First, the solutions to the two puzzles in Two Puzzles and a Meta-Puzzle.

Go look at that post first if you want to try to solve them yourself.

I’ll wait…

### First Puzzle: three prisoners with skullcaps

Briefly stated, a warden tells three prisoners he is going to sit them at a table and place black or white skullcaps on their heads randomly. Each of the prisoners can try to guess the color of their own cap or not. If everyone who guesses is correct, the prisoners win. If no one guesses, or any of them guesses wrong, they lose.

The simple strategy is for the prisoners to designate a guesser. Larry, Curly, and Moe agree that Larry will guess that his cap is white, and the other two will do nothing. There are two possible situations, either Larry has a black cap or a white one. This gives the stooges a 0.5 probability of winning.

Groucho, Chico, and Harpo are smarter than that. They agree that each of them will look at his brother’s caps, and if they see two caps of the same color, they will guess that their own cap is the opposite color; otherwise they will not guess. There are eight possible arrangements:

Groucho | Chico | Harpo | Action | Outcome |
---|---|---|---|---|

White | White | White | All three guess black | Lose |

White | White | Black | Harpo guesses Black, other two do nothing | Win |

White | Black | White | Chico guesses Black, other two do nothing | Win |

White | Black | Black | Groucho guesses White, other two do nothing | Win |

Black | White | White | Groucho guesses Black, other two do nothing | Win |

Black | White | Black | Chico guesses White, other two do nothing | Win |

Black | Black | White | Harpo guesses White, other two do nothing | Win |

Black | Black | Black | All three guess white | Lose |

### Second Puzzle: 100 prisoners with boxes

Note that this puzzle is often stated elsewhere with the prisoners getting to open only 50 boxes each. I prefer 90 because the prisoners’ success with 90 is more striking.

Others have written detailed explanations of this puzzle. Here is a good solution with the underlying math.

Put simply, the Marx brothers and their cousins assign a number to each of them, from 1 to 100. When each of them gets into the room, they open the box with their own number. If they find someone else’s name, they open the box with the number assigned to that person, and repeat as necessary.

By agreeing to this ordering and following it as they guess, the prisoners form themselves into loops, where each prisoner in a given loop traverses the entire loop before reaching his own name.

Opening 90 boxes each, the prisoners win if no loop is longer than 90 prisoners. The probability of success is roughly 0.895. Opening 50 boxes only gets a success rate of about 0.31, which is why I prefer the 90 box version — I’d rather see the prisoners improve their chances from 0.00003 to 0.895 instead of from 0.00000000000000000000000000000008 to 0.31.

To help explain the solution, imagine that there are just three prisoners, and they each get two guesses. Larry, Curly, and Moe select at random, giving each of them a 2/3rds chance of success. That gives them an overall success rate of (2/3)^3, or 8/27, roughly 0.30. The Marx brothers assign themselves numbers:

- Groucho
- Chico
- Harpo

There are six ways the names can actually be distributed in the boxes:

Groucho | Chico | Harpo | Longest Loop | Outcome |
---|---|---|---|---|

1 | 2 | 3 | 1 | Win |

1 | 3 | 2 | 2 | Win |

2 | 1 | 3 | 2 | Win |

2 | 3 | 1 | 3 | Lose |

3 | 1 | 2 | 3 | Lose |

3 | 2 | 1 | 2 | Win |

By guessing this way, the Marx brothers have improved their probability of success from 0.30 to 0.67. For more on why this works, read the meta-puzzle solution.

### Meta-puzzle: Gerrymandering Probability

Gerrymandering is a term used in politics to describe setting up voting districts to give advantage to one party over another. It includes two techniques: packing and cracking. Suppose you have two political parties: A and B.

“Packing” refers to lumping as many as possible of party A’s voters into a small set of districts, giving party A overwhelming majorities there.

“Cracking” refers to spreading out party B’s voters across many districts so that party B has slim (but hopefully reliable) majorities in those districts.

The result is that party A has huge margins of victory, but ends up with fewer victories, and hence fewer votes in whatever legislative body we’re talking about, while party B has small margins of victory, but ends up with more votes in the legislative body.

The two puzzles apply this principle with their outcomes. If you know of more puzzles that allow for this technique I’m eager to hear about them.

#### Skullcaps

The probability of guessing the color of a black or white skullcap is 0.5. Common sense says that there is no way to change that, and neither solution does: the stooges have one correct guess, and one incorrect guess, while the Marx brothers have six correct guesses, and six incorrect guesses (check the table above).

The key is how the correct and incorrect guesses are organized. Using the Marx brothers’ technique, when they guess wrong they all guess wrong, but when they guess right, only one of them guesses right while the other two sit out. In political terms, the six incorrect answers are “packed” into two unsuccessful outcomes, while the six correct guesses are “cracked” into six successful outcomes.

#### Boxes

The same principle applies to the boxes. Taking the simpler example of three prisoners, the average number of boxes a prisoner should expect to have to open to find his name is (1+2+3)/3 = 2.

Laying out all the possible arrangements for the stooges would take too much space, since there are 6 different ways the boxes can be laid out, and then 6 different ways each stooge can guess, for a total of 6^4 = 1296 possible arrangements overall. But consider one arrangement of names in the boxes — 1. Larry, 2. Curly, 3. Moe — and the guesses Larry can make:

First Guess | Second Guess | Third Guess | Note | Number of Guesses to Find His Name |
---|---|---|---|---|

1 | 2 | 3 | He wouldn’t make the second or third guess | 1 |

1 | 3 | 2 | He wouldn’t make the second or third guess | 1 |

2 | 1 | 3 | He wouldn’t make the third guess | 2 |

2 | 3 | 1 | He loses | 3 |

3 | 1 | 2 | He wouldn’t make the third guess | 2 |

3 | 2 | 1 | He loses | 3 |

For the Marx brothers, again if they decide to use 1. Groucho, 2. Chico, 3. Harpo, there are six possibilities for the boxes:

Groucho | Chico | Harpo | Groucho’s Guesses | Chico Guesses | Harpo Guesses |
---|---|---|---|---|---|

1 | 2 | 3 | 1 | 1 | 1 |

1 | 3 | 2 | 1 | 2 | 2 |

2 | 1 | 3 | 2 | 2 | 1 |

2 | 3 | 1 | 3 | 3 | 3 |

3 | 1 | 2 | 3 | 3 | 3 |

3 | 2 | 1 | 2 | 1 | 2 |

So in each puzzle, the probability of success in each individual instance is never changed, but by figuring out a way to pack the failures and crack the successes, the overall success rate can be significantly changed.

Itai ZukermanThere’s actually a second solution to the 3 hats problem with 75% probability of success:

player 1 goes with the majority; otherwise passes

player 2, if 1 and 3 agree, passes; otherwise goes with what player 1 wears

player 3, if 1 and 2 agree, passes; otherwise goes with what player 1 wears

Pingback: Three Prisoners with Skullcaps — An Alternative Solution « Geoff Canyon’s Appeal to Authority