A Hat Guessing Game

Problem: There are $100$ prisoners. A warden decides to play the following game:

• Each prisoner is given a hat with a number from $1$ to $100$ written on it (not necessarily distinct).
• They can see the numbers of everyone else's hat but not their own.
• They cannot talk to each other or signal in any way once the game starts.
• They can however coordinate the day before the game starts.
• Each prisoner is taken into a room one by one and has to guess the number on their own hat.
• If any prisoner guesses their own hat correctly they are all let free, otherwise they are all executed.

Do the prisoners have a strategy to ensure they are all set free?

Thoughts: There are only $100$ options and $100$ prisoners so intuitively there should probably be a solution to this problem. Because if you imagined you had a multi choice question with $100$ options and you had $100$ different guesses then surely you would get the right answer eventually.

One of the first strategy we might think of then is to have every prisoner guesses a different number for their own hat. That is one prisoner guesses $1$, another prisoner guesses $2$ and so on. However this strategy doesn't work.

The reason this doesn't work is because each prisoner is not answering the same question. Each prisoner is answering a different question which is "What is the number on your own hat?". This is as if you had $100$ different multi choice questions and one attempt on each one. In such a situation it's possible that you get every question wrong.

So in order to solve this question we need to rephrase the question. Instead of each prisoner guessing their own hat number they need to be guessing some other quantity that is the same for all prisoners.

What if instead of guessing their own hat number they guessed the sum of all the hats of all the prisoners. If they could guess this correctly then the can determine their own hat number by subtracting the sum of all the other prisoners hats from the total sum. In fact it's enough to correctly guess the sum modulo $100$ because the value of their own hat is between $1$ and $100$. Each possibility leads to a different value of the total sum mod $100$.

Solution: Each prisoner gets assigned a number $1$ to $100$ before the game starts. Then each prisoner guesses the sum of all the hats modulo $100$ to be equal to their assigned number. This way exactly one prison will be correct.

Every prisoner then guesses their own hat number to be equal to their assigned number minus the sum of all the other prisoners hats modulo $100$. This way exactly one prisoner will correctly guess their own hat number.

Example: If there are two prisoners, two hats and the numbers are between $1$ and $2$ then either the two hats are either different or the same. This corresponds to the two possible sums modulo $2$. Either the sum of the two hats is even or odd.

Prisoner $1$ assumes the two hats are different. Prisoner $2$ assumes the two hats are the same. One of them will be correct.