mathematics - One hundred and one hats

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.

Answer

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.