Gerrymandering Probability

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
By guessing this way, the Marx brothers have a 0.75 probability of winning.

Second Puzzle: 100 prisoners with boxes

Again, briefly: a warden tells one hundred prisoners he has a room with one hundred closed numbered boxes, with each prisoner’s name in exactly one box. The prisoners are let into the room one by one and each is allowed to open ninety boxes — all but ten. If all the prisoners manage to find their own name, they win. If any of them fails, they lose.

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.

The stooges and all their cousins, simply opening the boxes at random, have a probability of success of 0.9^100. That’s about 0.00003. In the 50 boxes version those numbers are 0.5^100 and 0.00000000000000000000000000000008.

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:

  1. Groucho
  2. Chico
  3. 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
The total number of guesses Larry makes is 12, across 6 cases, for an average of 2 guesses, which is expected.

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
The total number of guesses is 36 across 3 Marx brothers in each of 6 cases, for an average of 2 guesses each. But again, notice how the Marx brothers managed to group all their failures together. It is never the case that one brother successfully finds his name in less than three guesses while another fails. This is the ideal case — in the actual puzzle, there will be cases where 91 or more prisoners fail to find their names and some or all of the rest are successful.

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.

Advertisements

2 thoughts on “Gerrymandering Probability

  1. Itai Zukerman

    There’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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s