6 ms·
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 m
by 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.