3 ms·
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 alway
by SilasX 9y 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 9y 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.