It’s obvious that the prison is overcrowded. So no matter what happens, the warden has just freed up 100 beds.
One aspect that I’m glad he emphasized:
The trick to this puzzle (and a number of others) is that while no strategy can change the outcome on an individual level, what you can do is alter how the outcomes are correlated. If the goal is “everyone has to succeed”, then what you want is for everyone to lose at the same time. It’s bad to sprinkle individual losses over all of the outcomes, since any one of them causes a loss for everyone. But if you can concentrate the losses so they happen all at once, you can have more outcomes where everyone wins.
In this case, the concentration happens because when there is a 51-or-more loop, everyone in that loop loses, because they all start at the maximum distance away from their number.
The thing that still confuses me is how if you pick the box with your number on the lid, the box that contains your number must be in the loop.
I was able to internalize it by running through all possibilities if there were only 3 instead of 100. Or, rather, doing that led me to acceptance of the fact. I still don’t fully understand the why of it.
Consider that you will always get there eventually, even in the worst case. The numbers in the boxes are a permutation–i.e., every number is there, with no duplicates. Your number is in one of the boxes.
So you follow the chain. If a little demon was making things hard for you, it could swap numbers around so that you kept going to some other box. But eventually it would run out of numbers, and the last one would have to have your number in it. That would be the case for a 100-long loop.
There’s no demon, so in practice the loop is sometimes shorter. And when everyone is in a loop of 50 or less, they win.
Another way of looking at it:
Think of every box as the link in a chain. How many links connect to it?
It can’t be just one (or zero). Every box has another box pointing to it, and itself points to another box. So it must connect to at least two other links.
Could it be more? Well, a box only has one slip of paper inside it, so it can only point to one other box. And because it’s a permutation, there’s one and only one box that connects to it.
Therefore, each link connects to exactly two other links. Which means that loops are the only possible configuration. A chain can’t just end, nor could you have one shaped like a 6 where you start in one place and end up trapped in a smaller loop. An O shape is the only possibility when each link connects to two others. Which means that every box eventually loops back to itself.
Think of it this way:
Every box can be considered as two numbers and a direction. The first number is the box number, the second is the number inside.
34 > 14
14 > 87
Every number only appears twice. Once on each side of the arrow. You can easily pick the one with your number at the front. This has to lead to a chain that either loops back to a later number or loops back because it contains your number. but it can’t be the first option, because every number, except your first one, will already have appeared twice.
If it helps, think of the contents of the boxes as being the result of a LOT of repeated swaps.
Originally, each box contains its own number (box 1 contains 1, box 2 contains 2, etc). You can generate any distribution of numbers by repeated swapping of the contents of pairs of boxes.
Example (with 4 boxes). If you want to get to 3-1-4-2 from 1-2-3-4, you can get there by swapping 2 boxes at a time:
1-2-3-4
3-2-1-4
3-4-1-2
3-1-4-2
That took 3 swaps. You can simply reverse the process and get back to 1-2-3-4.
Editing this:
This wasn’t as clear as it is in my head. But the reason is you start with your own is to avoid ‘cycles’, like 1-3-2-4. Since 1 is in its own box, starting anywhere else will mess you up. But if 1 is not in its own box, a series of swaps will (eventually) get it back to box 1. And ditto the other boxes. So you want to start with your own box.
Why not? Is there a rule that states that a box cannot contain its own number?
The slips (presumably) are randomly placed in the boxes. So if the first box chosen for a slip is Box # 33, then there there is a 1% chance that Slip # 33 will be placed in that box.
Also, it could be a two-box loop, where two boxes contain the number of the other box. (Box # 22 has slip #44; Box # 44 has slip #22.)
A box can connect to itself. To be clear, an “other box” can be itself. The point is that it has exactly one slip of paper inside it, and that there’s exactly one slip of paper with the box’s number on it.
Correct. But to use your analogy of a chain, the chain could contain 1 link, or 2 links, or any number of links up to 100.
The important thing to remember is that if the chain contains 3 or more links, the starting and ending links are also connected to each other.
It is the connections that I am speaking of, though. Of course, normal chains aren’t bendy enough that a single link can really connect to itself, but we can at least imagine it. Or just imagine links connected by strings. Each one has an incoming and outgoing string. That might be the same string, or it might go through several other links before coming back to itself.
Really, you can just demonstrate it to yourself on paper. Draw some collection of dots. Connect them with lines, with the only rule being that a dot must have exactly two lines connecting to it. You’ll find that single loops are the only possible outcome.
Thanks very much to everyone who helped with my question. It’s the spookiest part of the logic but I get it now.
My problem was that I was visualizing a bunch of discrete loops like in the video as separate things and wondering why my number can’t be in that box in the other loop over there.
I can’t even comprehend the genius that it took to figure out the solution.
Referring to what I mentioned before about permutations, every permutation can be written as a product of disjoint cycles. Maybe it is not obviously obvious, but if you just take a sheet of paper and try doing it to some random permutation you will immediately see how to factor it.
Is it really known for sure who originally proposed the problem? Ususlly these things come up at dinner after everyone has has a couple of drinks and there is a computer scientist in the party.
Perhaps this will help.
You are going to open boxes with the lids labelled by a number. Inside the box will be a paper with a number on it. There are one hundred lids and one hundred papers and each is numbered one to a a hundred with every number appearing exactly once on a lid and once on a paper.
So you start recording the numbers on the lids and the numbers on the papers as you encounter them. Let’s say your prisoner number is 42. You start with lid 42. This might be what your list looks like:
lid 42
paper 88
lid 88
paper 19
lid 19
paper 62
lid 62
paper 5
lid 5
paper 70
etc
Notice that you always have pairs of numbers. Each number on a paper will be followed by the same number on a lid.
Now notice that the first number on your list was lid 42. This means that the number before it must be paper 42. And that’s the paper you are looking for.
The boxes and lids form a loop and any loop that begins with lid ## must end with paper ##.
Thank you very much for this, it finally makes intuitive sense to me.
It’s not like someone came up with the puzzle on a lark, and then someone else came up with the solution. Rather, some mathematician was studying permutations, and the probability of having loops of various lengths, and then came up with the puzzle (to which he already knew the solution) based on that.
According to the Versatarium video, yes.
From what I understood of the Versatarium video, that’s more or less exactly what happened.
I’ll have to watch it again tonight when I get home to be sure, but I do know that he said that the guy that came up with the puzzle was not the person who came up with the answer.
And that’s assuming, of course, that the Versatarium video is correct.
Veritasium, as in latin “Veritas”, Truth, and -ium, suffix meaning it’s an element. See also Stadium (the element of stadia) and opium (the element of opes).
Yes, and his chanel symbol is made up to look like an element of the periodic table. I believe in one of his early videos, he explicitly said that the name meant, “An element of truth.”
That’s not to say that he’s necessarily the authority on all things, I’m pretty sure there were a few things that he has had to correct over the years, but he’s gotten enough of a reputation that for something like this, I have no problem taking his word for it unless a better source says otherwise.
See also Unobtanium, which is an element, vs Macguffinite, which is a mineral. 