Some of you may have already seen this riddle/puzzle in the recent Veritasium video linked below.
There is a prison with 100 cells numbered 1-100 and a prisoner in each cell. As with all prisons in mathematical riddles the warden is a psychopath and offer the prisoners their freedom if they can beat a difficult riddle.
There’s a room with 100 boxes numbered from 1-100. Slips of paper with the numbers 1-100 are randomly distributed one into each box. The prisoners may enter one by one, search up to 50 boxes, and then leave through a separate door and not interact with the other prisoners until the whole 100 have passed through.
If every one of the 100 prisoners find their cell number in the up to 50 boxes they check everyone goes free. If any one of them fails, they all … doesn’t really matter for the puzzle does it?
If they pick boxes at random there is an extremely slim chance they’ll go free. I ran a simulation with 5000 runs and they didn’t succeed once. Follow the strategy from the Veritasium video and the odds skyrocket to above 30%. (Also verified in my simulation.)
Give it a think before watching the video, and don’t post about the solution without a spoiler … at least not for a few days or until there’s a page of replies, whichever happens first.
Well, 1 reply is an entire page of replies on Discourse. As for the puzzle, it’s an oldie. I would have never been able to solve it myself, but made immediate perfect sense when explained the first time I saw it, (normally it’s framed as a High School locker problem.)
Yeah, I should probably have written “Some of you may have already seen this riddle/puzzle in the recent Veritasium video or some of the many other places it’s been discussed over the years.”.
I have seen this. Didn’t think of the ‘solution’ myself, didn’t even try that hard. It’s a good strategy to use but still fails 2 out or 3 times. However, if Monty Hall is the warden and lets you switch doors your odds improve to success 1 out of 2 times.
Yes, but it’s orders of magnitude better than randomly guessing. And while I get that and why it works, it still seems weird you can impose an order like that post hoc and have it make that much of a difference.
I think it was Stand Up Maths that did this about a year back that I first saw this puzzle.
Though he did it with a somewhat smaller sample size, he actually ran the “experiment” with volunteers. Some groups knew the solution, some didn’t. The ones that did won about a third of the time, the ones that didn’t never won.
Anyway, I disagree with the counterintuitive part. Admittedly, I didn’t come up with the solution myself, but as soon as I heard it, I thought it made perfect sense.
I assume that it wouldn’t be all that hard to work out the probabilities of success if you change the number of boxes or the number of chances.
I’m pretty sure that, for large n, the probability for success using this method approaches some constant value, and n=100 is certainly large enough that that constant value would be an excellent approximation. Of course, the probability of success for a non-method “method” of everyone choosing randomly falls off exponentially for large n, and n=100 is large enough that it’s basically zero (somewhere in the neighborhood of 1 in 10^30). Even for n=10, the random method still has less than a 0.1% chance.
It gets there. In the video (which I actually watched last night), he shows that it approximates towards ~.3. There actually is a significant change from 100 to 1000, but as the number goes up, the change gets smaller rapidly, showing that it converges.
But my question was more changing the parameters. Instead of 100 boxes and 50 chances, having only 40 chances or as many as 60.
You need to figure out the best you can do with an arbitrary method (then come up with a method that achieves this bound). If I understood the OP, you are essentially dealing with random permutations (like shuffling a deck of cards).
After a fashion. As the video points out and I still can’t quite get my head around, if a malicious warden sneaks in and creates a loop longer than 50 to guarantee failure, the prisoners can defend against that by adding 5 (or whatever arbitrary change) to each box number but not to the ticket numbers.
Apparently changing how you interpret box numbers actually rearranges the loops into a different set of loops. I can’t quite wrap my head around that yet.
I assume that by the same token, if you had a benevolent warden who snuck in to ensure no loops were larger than 50 – being able to ensure that with only a single switch – instead of the 100% chance to win, if the prisoners add 5 to each box they would be right back down to ~31%.
I also don’t buy that each individual prisoner still has a 50% chance. Well, rather, I believe it, but it doesn’t make sense to me yet. Using this strategy you aren’t checking 50 out of 100 possibilities, you’re checking some number of loops out of the total number of loops in the actual room. It’s not immediately obvious to me that this should also be 50%.
EDIT: Great riddle, by the way. I hadn’t heard it before, and it took me about 15 seconds to correctly identify that I would never come up with the right answer.
Okay here’s where I’m having trouble. I’m thinking of the random distribution of loops in the room. Why isn’t there a 50% chance that there is at least one loop 51+ long?
I would think the way to create a random number of randomly sized groups out of 100 numbers would look something like this:
Pick a random group size from 1 to however many elements you have left.
Pick that many elements at random and remove them from the list.
Go back to step one until you run out of items to pick.
It seems like this process should give you a random distribution of loops, but that very first iteration of step 1) chooses the first group size to be between 1 and 100. If it picks anything between 51 and 100 – literally a 50% chance – then the prisoners lose.
Okay, well, I guess that’s why any individual prisoner still has a 50% chance to win or lose using the loop strategy. That at least makes intuitive sense to me.
But then shouldn’t 50% of all rooms have a loop of 51+ elements? Something still isn’t clicking for me with the 31%.
Would my little three-step process generate the same distribution of loop sizes as the process in the riddle generates?
Correction: You are checking exactly one loop; the loop that includes your number. That part still isn’t intuitive to me either, but I was never good with pointers.
Actually, about 69% of the rooms have a loop of greater than 50 elements. That’s why the prisoners have a ~31% of success. The length of the loop is not a random number picked between 1 and 100, it is based on a kind of bell curve that starts small and gets steep as it approaches 50, then more gradually declines after. There are more chances for longer loops than shorter loops.
My understanding of the 50% of prisoners is not on a single run, but if you ran it many times, then 50% of the prisoners would find their number, though for about 40% of them, it is for naught, as their fellow prisoners do not find theirs.
If you have one loop of 60, then 40 of the prisoners will find their number, in a single loop or in multiple, even though 60 do not. Same with a loop of 51 or 70. The greater the size of the loop, the lower chance it has of existing, where a loop of 100 size would have about the same chance of coming about as the prisoners all finding their number randomly.
So, between the ~30% of runs where everyone finds their number, and all the runs where there is one loop greater than 50, but other loops that are less, it comes out to 50% of the prisoners, overall, find their number.
I just realized something about my little algorithm: the first loop isn’t necessarily the largest loop. First loop could be 10 elements then the second one could be 90, for example.
Can you put an actual number on that chance? My function has exactly 1% chance to have a single loop of 100 elements: It can only happen on the first pick, and that first pick has to roll a 100 out of 100.
By contrast, having a hundred loops of one element each would mean you rolled a 1 out of 100, then 1 out of 99, etc… I have no ability to estimate the result of that, and it seems daunting to calculate. I suppose it could be 1%.
If you think of shuffling n numbers, the probability that the resulting random permutation has a single cycle is precisely 1/n. Or am I missing something?
If n=100, the average maximum cycle length is approximately 62.74.
Sure, but the setup of the puzzle doesn’t generate a a random number of randomly sized groups … or, it is, but it’s picking the specific distribution of group size that arises when randomly ordering 100 numbers and then arranging them in loops by their position in the list.
Imagine you do this with 4 numbers instead, to get a manageable number to work out in detail. There are 24 ways these can be arranged. If you write them out you can find manually that there are 6 permutations where the longest loop is 4, 8 where the longest loop is 3, 9 with a longest loop of 2, and 1 with a longest loop of 1.
That’s a 25% change of longest loop equaling 4, 33.33% change of the longest being 3, 37.5% chance of the longest being being 2% and 4.17% chance of the longest being 1.
If you start by picking a random loop length and iterate as you suggest you get the following distribution:
Loop length 4, 25%,
Loop length 3 33.33%
Loop length 2 33.33%
Loop length 1 8.33%
