4 ms·

Can you explain to me why it is guaranteed you will be in a loop with your number?

by justadudeama 8y ago

deleted 8y ago
[deleted]
deleted 8y ago
[deleted]
laurentl 8y ago
The entire set-up (the numbers in the boxes) is a permutation. In other words, it’s a function s that maps bijectively from [0, n-1] to [0, n-1], or to put it more simply: for each i in [0, n-1] there is exactly one value j such that s(j) = i. If you take i_0, then i_1 = s(i_0), then i_2 = s(s(i_0))... and so forth, at some point you will encounter a value you have already seen (because you can only visit n different values at most), and from that point onward you will loop. The trick is that the first value you will see twice MUST be i_0 (your starting point). If not, that is if s(i_k) = i_m where m > 0 (and i_k is the last value before you loop back) then s(i_k) = s(i_{m-1}). This means that i_k = i_{m-1} which is in contradiction with the fact that i_k is the last value before looping (i_k was already visited at step m-1) Edit to answer TFQ: if your start with your own number as i_0, the proof above shows that at some point you will loop back to it. Then it’s a question of whether you loop back in 50 moves or less.
SilasX 8y ago
To try a simpler explanation: 1) You will be in a loop (by a property of how permutations and hashing work). 2) Using the algorithm in the solution, you always go to the box indicated by the number in the drawer you open. So if you start with "your" number's drawer, that it is "pointed to" by the drawer with your number in it. So your number is part of that loop.
- daxfohl 8y ago
  * Thus you will never be in some other loop. Loops are disjoint. Disjoint circles, not train tracks that interconnect. Just loops. Think about that and realize it. * This strategy guarantees you'll be in your loop. ("Unfortunately" you'll be at the end of that loop: the box that points to your number. But still, in the loop, which is the point). * Thus if there are multiple loops, all of length 50 or less, you'll get your number before your number is up. * And math shows that if there are 100 nodes in a randomly unidirected graph, 30% of them contain no loops greater than length 50. So if everyone follows this strategy, 30% chance they'll win.
savanaly 8y ago
Every box points to a box and is pointed to by a box. If at first you try box 3 and it doesn't contain your number 3, then your number 3 is out there and its box points to the one you tried. Thus its box is in your chain and has your number.

Can you explain to me why it is guaranteed you will be in a loop with your number?

deleted 8y ago

[deleted]

deleted 8y ago

[deleted]

laurentl 8y ago

The entire set-up (the numbers in the boxes) is a permutation. In other words, it’s a function s that maps bijectively from [0, n-1] to [0, n-1], or to put it more simply: for each i in [0, n-1] there is exactly one value j such that s(j) = i. If you take i_0, then i_1 = s(i_0), then i_2 = s(s(i_0))... and so forth, at some point you will encounter a value you have already seen (because you can only visit n different values at most), and from that point onward you will loop. The trick is that the first value you will see twice MUST be i_0 (your starting point). If not, that is if s(i_k) = i_m where m > 0 (and i_k is the last value before you loop back) then s(i_k) = s(i_{m-1}). This means that i_k = i_{m-1} which is in contradiction with the fact that i_k is the last value before looping (i_k was already visited at step m-1) Edit to answer TFQ: if your start with your own number as i_0, the proof above shows that at some point you will loop back to it. Then it’s a question of whether you loop back in 50 moves or less.

SilasX 8y ago

To try a simpler explanation: 1) You will be in a loop (by a property of how permutations and hashing work). 2) Using the algorithm in the solution, you always go to the box indicated by the number in the drawer you open. So if you start with "your" number's drawer, that it is "pointed to" by the drawer with your number in it. So your number is part of that loop.

daxfohl 8y ago
* Thus you will never be in some other loop. Loops are disjoint. Disjoint circles, not train tracks that interconnect. Just loops. Think about that and realize it. * This strategy guarantees you'll be in your loop. ("Unfortunately" you'll be at the end of that loop: the box that points to your number. But still, in the loop, which is the point). * Thus if there are multiple loops, all of length 50 or less, you'll get your number before your number is up. * And math shows that if there are 100 nodes in a randomly unidirected graph, 30% of them contain no loops greater than length 50. So if everyone follows this strategy, 30% chance they'll win.

savanaly 8y ago

Every box points to a box and is pointed to by a box. If at first you try box 3 and it doesn't contain your number 3, then your number 3 is out there and its box points to the one you tried. Thus its box is in your chain and has your number.