The 10 x 10 arrangement is a red herring.

I was working along the lines of the idea in the video but I kept thinking that a path forward could turn into a loop in front of my starting box. But then that would require two pointers to the same box in front of me. So not possible. Loops can't have any hanging tails. I kept thinking loops were bad and I wanted a long path. I was confused. I had it backwards.

Since there can only be one loop longer than 50 the captain just needs to cut it into two shorter loops. Nice twist.

https://en.wikipedia.org/wiki/100_prisoners_problem

I was wondering whether other cycles might also be relevant. Like e.g. for the relation n --> m if Box n contains the number 100 - m. Probably not.

A+ puzzle. B- red herring.

------------------------------------------------------------------

Very good.

The classical version of this problem doesn't have the captain - that was my little flourish - and essentially reduces to the question of "what is the probability that for N consecutive integers there will be a cycle of length > N/2?" The answer turns out to approach ln(2) as N approaches infinity, so even for very large N they survive an amazing 30% of the time at a minimum.

I love how elegant the solution is, considering the naive approach has them surviving at a rate of 1:2^N, and with the twist the solution could basically be explained to a 10 year old.

More here if you're interested: https://en.wikipedia.org/wiki/100_prisoners_problem

As an aside, I'm a data warehouse dev, and cycle detection in parent-child relationships stored as a self-referencing foreign key has been the bane of my existence and the cause of crashes/timeouts in more than one of my CTEs, so it's somewhat close to my heart. Those cycles have tails.

Edit: just saw your edit, didn't pay that much attention to the exact method you suggested - obviously I knew you meant to split the cycle into 2 smaller cycles, which is trivial.

------------------------------------------------------------------

Aaron might (and should) pull me up on the rather loose statement that the convergence is absolute. The convergence, in the very technical sense of that term, only exists for N even (Aaron - is that right?)

The prisoners and captain need to settle on a common numbering scheme for the lockers ahead of time. While this might still be possible if the lockers were haphazardly scattered about the locker room, knowing it's a 10x10 or any such array makes it clear a common numbering scheme is easy for the prisoners to come up with. So not irrelevant.

One can get lucky and have a few fixed points say k that distribute like e^-1/k! seen above. If people aim for their numbers and others avoid those it may help.

In a way you want to use the fact the one before made it to avoid going through the fixed points of the other guy if possible if he had any. So the other guy can look for their own fixed point possibility (that would have hurt the other guy if chosen) and you must avoid securing 100% going through their potential fixed points by not looking in the locker/box of the others as original option. To avoid fixed points of others you must follow a path that would not lead to a fixed point but how you can do that unless you develop a sequence of choices that are not random that avoids taking you to fixed points. The captain may try to help the first guy that then helps others too effectively. To be continued.

You could have 101 boxes and everyone could still do it in 50 goes. The array sucks.

Linked list

Consider this specific permutation. Consider the finite group consisting of its powers. Consider the orbits of the elements of the set that group acts on ( numbers 1-100). Apply group theory.

For example the above reasoning i started has lead me to conclude that it may be useful to develop a sequence of checking boxes that is not random but planned to exploit good breaks like you need to avoid checking boxes that can be the fixed solutions of others but it helps to get lucky and check your possibility of fixed solution. So you need to check your box and then develop a process that doesnt take you to a fixed point of others that is a wasted move. Also others need to build on your sequence to avoid going through things that hurt all ie there must be a way that all help each other by the sequence they follow that exploits some natural analysis of the permutation like maybe see it as product of permutations etc some transformation back to where it started from or something that is very different than randomly opening boxes.