3 ms·
This was my aha moment. I was thinking, the solution presented seemed not only invalid but ill-defined, as you could hit a cycle and still have picks left. Wi
by daxfohl 9y ago
This was my aha moment.
I was thinking, the solution presented seemed not only invalid but ill-defined, as you could hit a cycle and still have picks left. With this, it totally makes sense why it works: if there are disjoint cycles, this strategy guarantees that each prisoner is on its own cycle. And I guess the math works out that in unidirected graphs of 100 nodes, 30% of them contain only disjoint cycles of 50 or fewer nodes.
- sigotirandolas 9y agoBecause of the way that the problem is set up (each of the 100 numbers is in one of the 100 lockers), it can always be written as a list of disjoint cycles (mathematically: every permutation can be written as a product of disjoint cycles). So, by starting in your own locker, you will eventually end up finding your own number. The only constraint is that everyone has to do it in 50 tries or less, i.e. there's no cycle of length >50.