Thanks for asking the question, OP. I loved that video/explanation. What an incredibly clever way to look for “your” dollar.
OK. You walk in and the boxes are scattered everywhere, randomly around the room. You could say that you’ve previously agreed that the boxes are enumerated by distance from the door. What are you going to measure with?
My beef is with the unstated assumption that the boxes can be enumerated at all.
P.S. I like the puzzle very much.
Well, how about you walk into the room, take the wall that the door is on as the starting point, and go right to left (right being defined when facing into the room through the door) picking the next yet-uncounted box that is to the left of the one you picked before and is closest to that wall and arranging them behind you in a 10x10 grid. Then you use the grid to “number” the boxes?
So you’re now measuring angles instead of distances. Got a hundred theodolites handy?
I’d have been happier if the puzzle was stated that the boxes are in a 10 x 10 grid. That’s implied by the drawing, of course, and as I said I like the puzzle, but I tend to dissect puzzles and the ability to enumerate without resorting to some real world accuracy is just a teeny gap for me.
Okay, I haven’t watched the video, but I’m very intrigued by the 100 prisoners problem!
My question is, for one particular prisoner searching for his number, does following the 100 prisoners strategy (starting with his box number and then going to the box matching whatever number he finds,) increase his own chances above 50%?
Or is it just that the strategy “synchronizes” each prisoner’s chance of success to a much greater extent than if they were searching randomly, so that each prisoner still only has a 50% chance to succeed, but overall they have a 30% chance of all succeeding?
Each individual prisoner’s chances are unchanged. The increase is due to, as you say, the chances of success being “synchronized”.
“Matching the boxes” is fairly well-known in puzzling circles. There’s a vaguely related puzzle which should be presented first. It’s much easier than “Matching the boxes” but exhibits a similar “paradox.”
~ ~ ~ ~ ~ ~ ~
Help Four Prisoners Go Free
The warden calls in his four prisoners and announces that that night will be their last night in jail. The next day, depending on the success at a contest, all four will be released … OR all four will be hung by their necks until dead.
The warden explains the following rules and leaves the prisoners free to discuss the contest that evening. But at bedtime they will be separated and no further communication will be permitted.
The next morning each of the four prisoners will be assigned a hat, either red or white according to a coin flip, but cannot see the color of his own hat. Each prisoner will be shown photos of the other three prisoners with his colored hat. Each prisoner will then write one of three things on a piece of paper:
[ul][li]My hat is red.[/li][li]My hat is white.[/li][li]Pass.[/li][/ul]
If any prisoner misguesses his hat color, then all four will die.
If all prisoners write “Pass,” then all four will die.
If at least one prisoner guesses and all guessers guess correctly, then all four prisoners will be set free.
How should prisoners play to maximize their chance? (Solutions in Spoiler-boxes, please.)
If you see three white hats, write “My hat is red”; if you see three red hats, write “My hat is white”; else pass. I believe that gives a 50-50 chance of living, as there are exactly three white hats a quarter of the time, and exactly three red hats a quarter of the time.
If all four prisoners guess their hat colour randomly they have a 6.25% chance of going free.
My first thought is that they should agree that 3 pre-determined prisoners chose “Pass”. The 4th prisoner guesses his hat colour. If he guesses randomly all four prisoners have a 50% chance of going free. The question is if the 4th prisoner can do better than chance.
I did a quick chart of the 16 possible permutations and checked if the 4th prisoner picking the colour he sees only 0 or 1 of in the pictures does better. Unless I made a mistake, it doesn’t help.
I feel like there should be a better strategy (otherwise the puzzle seems too easy). I’m going to try to resist the temptation to look at other answers until I’m sure I can do better than 50/50.
[SPOILER]Okay, I’ve come up with a scheme that a) doesn’t require certain prisoners to pre-agree to pass (which seems almost like cheating) and b) has a better than 50% chance of the prisoners going free. I’m not sure it’s the best possible scheme, and it’s not terribly elegant, but I’m going to go to bed anyway 
The prisoners should agree to follow this chart to decide what to write:
Sees : Writes
3 Red : My hat is White
2 Red : Pass
1 Red : My hat is Red
0 Red : My hat is White
In the 1 case where all hats are red the prisoners will be executed.
In the 4 cases where 3 of the hats are red the prisoners will be freed.
In the 6 cases where 2 of the hats are red the prisoners will be freed.
in the 4 cases where 1 of the hats are red the prisoners will be executed.
in the 1 case where all of the hats are white the prisoners will be freed.
They live in 11 of 16 cases, or about 69% of the time.
[/SPOILER]
[spoiler]Best I can do is 75%, which I think is optimal.
Clearly, we want to combine the losing cases. 3 guesses for each prisoner isn’t enough, no matter how we spread it out: 3 losses, plus 4*3 correct guesses, makes for only 15 combinations. So some prisoner must guess at least 4 times, and that means 4 losses across the 16 possibilities.
I imagine there are lots of possible answers, but here’s one:
0000 dddd
0001 ppp1
0010 pp1p
0011 0ppp
0100 p1pp
0101 0ppp
0110 dddd
0111 ppp1
1000 1ppp
1001 pp0p
1010 ppp0
1011 dddd
1100 ppp0
1101 dddd
1110 1ppp
1111 p1pp
The first column is red/white hats. Second column is what each prisoner guesses (p for pass). dddd means everyone died; all other cases are a win.[/spoiler]
One of the posted answers is correct:
[SPOILER]
Dr. Strangelove’s – excellent!
However there is an easier way …[/SPOILER]
Hint: The fourth prisoner was a “red herring.” Just solve for the three-prisoner case.
Okay, working based off septimus’ hint, I still can’t get to a great strategy…
Help three prisoners go free…
This one works out pretty well. If you see two red hats, you guess white, if you see two white hats, you guess red. If you see one of each, you pass.
If everybody has the same color hat, then everybody guesses wrong, but that’ll only happen a quarter of the time. Otherwise, only one person will guess, and they’ll guess right. Total odds of victory are 75%
However, I can’t get that to scale up to “Help Four Prisoners Go Free” right. The nearest I can get is a simple equivalent: If you see three white hats, you guess red, if you see three red hats, you guess white, otherwise you pass. This leads to a win half the time, (if one guy has a different hat color from the other three,) and everybody guesses wrong an eighth of the time (everybody has the same hat color.) The other 3/8 of the time, there are two hats of each color. Nobody guesses, and again they all die. You could get the same odds with the naive strategy of picking one guy to guess for the team, and having him flip his own coin.
BTW, I opened Dr. Strangelove’s spoiler box, but can’t yet figure out the rules by which his guys guess or don’t guess in each of those cases.
I don’t see what I’m missing.
[spoiler]It seems to me to move it up to the 4 person game, all you do is essentially eliminate the 4th prisoner. “Ed, you’re a good crook. But kind of dim. Just write pass.”
Then the other 3 prisoners play the game acting like Ed’s not even in the photograph.[/spoiler]
Oh, of course! Simple once you think of it… And as far as that goes, it can be the smartest one who passes every time. 
Ed’s been known to make mistakes counting to two.
My strategy was pretty confusing, so here’s a slight improvement in the description:
[spoiler]
First column is the distribution of hats, Red or White, on each prisoner (Andy, Bob, Chris, or Dave). Second column is what they’re supposed to guess. They don’t see their own hat, so half the table is redundant: for instance, the WWWW and RWWW rows have the same guess (R) for Andy. The WWRW and WRRW rows have the same guess for (p) for Bob, and so on.
The last column is whether they lived or died. You can see that 4 distributions (WWWW, WRRW, RWRR, and RRWR) lead to death, and that there are 12 wrong answers packed in them. For WWWW and RWRR, everyone guesses wrong, while for WRRW and RRWR, there are only two wrong guesses and two passes. Those 12 guesses fill out the rest of the table, where in all the “live” rows only one person guesses (correctly).
ABCD ABCD
WWWW RRRR D
WWWR pppR L
WWRW ppRp L
WWRR Wppp L
WRWW pRpp L
WRWR Wppp L
WRRW RppR D
WRRR pppR L
RWWW Rppp L
RWWR ppWp L
RWRW pppW L
RWRR WRWW D
RRWW pppW L
RRWR WppW D
RRRW Rppp L
RRRR pRpp L
Haven’t had the time to use septimus’ hint to simplify the answer yet.[/spoiler]
Thanks, that helps…
So everybody guesses Red if they see three white hats, but each person also has other guessing rules, usually involving if they see only one other person in a white hat:
Andy: If I only see Dave with a white hat, I guess Red then too. If I see only Bob or only Chris in a white hat, then I guess white.
Bob: If I see three red hats, then I guess red.
Chris: If I see only Bob in a white hat, then I guess White
Dave: If I see only Andy in a white hat, I guess red. If I see only Bob or only Chris in a white hat, I guess white.
[spoiler]That looks right to me. I find the “if X, then Y” description to be more confusing than a truth table, but whatever works.
As for the simplified version:
[spoiler]Andy is the slow one, and we tell him to always pass. We can ignore him as long as the other prisoners vote on every combination. Here’s the truth table I came up with:
0000 p111
0001 ppp1
0010 pp1p
0011 p0pp
0100 p1pp
0101 pp0p
0110 ppp0
0111 p000
The rule ends up bring really simple. If your partners match (ignoring Andy), then vote opposite them. If they mismatch, then pass. All of the bad guesses end up concentrating into the WWW/RRR cases (or WWWW/WRRR/RWWW/RRRR when including Andy).[/spoiler][/spoiler]
To each their own. I find the truth table useful for checking out each case, but feel that it’s easier to understand a strategy boiling it down to four “if, then” guessing rules than an eight-line truth table.