8
$\begingroup$

You are a prisoner. One day, the Warden summons you and ninety-nine others to see his hat collection.

"Bowlers and baseball caps. Stensons and sombreros. One hundred and one headpieces, each unique in the world," says the Warden.

"You are the smartest of prisoners in my domain, and by law I must offer you a chance at your freedom. So here is the game we will play. While you all are blindfolded, I will place a hat on each of your heads. I will also wear one myself. Once the blindfolds are removed, you will look around and know the identity of every hat except two: your own hat, and my hat. Yes, by then I'll be gone.

"You will all then guess, by secret ballot, the identity of my hat. Besides seeing what other people are wearing, these guesses are independent. No communication once the game begins.

"If everyone names my hat, you will all go free. But a single wrong answer means you can all walk yourselves right back to your cells.

"Good luck. I reckon you will need it, as I calculate your odds of winning at $2^{-100}$."

As the prisoners gather to discuss their strategy, someone asks you what should be done. What do you say?

A couple notes:

  1. Assume you can't cheat by looking at the brim of your own hat -- you really don't know what your own hat is.
  2. The solution I am aware of uses math beyond high-school level. Nothing too super powered, but something you might not be aware of if you weren't / aren't a math major in college.
Improve this question
$\endgroup$
1
  • $\begingroup$ I wanted to post Matt Parker's variation on the Prisoners in Hats puzzles as a new question but looking at this question, and especially its answer, it seems a bit too similar. What do you think? As a side note, I found it confusing that prisoners didn't seem to know in advance all possible hat shapes, I thought I had missed something, but the answer clearly relies on that. $\endgroup$
    – Didier L
    Commented Sep 11, 2019 at 21:21

1 Answer 1

Reset to default
8
$\begingroup$

Over all possible situations, each prisoner will guess right at most half the time. If we want to maximize the probability of all guessing right, we must make it so that all prisoners are correct in the same situations as each other. To do this, we must find a property of hat assignments such that it is flipped if any two hats are exchanged. This is one way to express that property:

Assign each prisoner a number from 1 to 100, and have the warden be 101. Also number the hats from 1 to 101. Consider the number of pairs of people such that the one with the larger number has the smaller hat. One possibility for the warden's hat makes the number even, and the other makes it odd (this is the parity of the permutation defined by the hat assignments).

If all the prisoners choose the one that makes the number even (all choosing odd is equally good), then they will be all correct half the time and all wrong half the time, which is the best possible chance of success.

Improve this answer
$\endgroup$
2
  • $\begingroup$ "all correct half the time ***, which is the best possible chance of success." - Why? $\endgroup$
    – klm123
    Commented Oct 24, 2015 at 8:52
  • 1
    $\begingroup$ Even a single person can not be correct more than half the time (see first sentence of the answer), as the distribution of the two hats the person does not see is plain random. Any creative way to circument that (communicating with other persons, looking into a mirror) is excluded by the problem statement, if not explicitly, then at least by spirit. As we need all persons to be right, it can not be more likely than a single person to be right. $\endgroup$
    – Michael Karcher
    Commented Oct 24, 2015 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.