## Jun 19 Prisoners in Rainbow Hats

This is the latest in the never ending stream of puzzles about prisoners in hats. For earlier parts see Prisoners in HatsPrisoners in Hats 2, 100 Prisoners with a Lightbulb and 100 Labelled Boxes. There were a couple of spin off prisoner puzzles from the main series, but they are about different structures of mathematics so I'll leave them out.

Right, with that over with, I present one of the harder prisoners with hats variations. Seven prisoner are sat around a table and each wears a hat which is either Red, Orange, Yellow, Green, Blue, Indigo or Violet. There is no guarantee on how many of each hat there is; it could even be seven of the same colour.

Each prisoner can see every other prisoner, but they cannot see the colour of their own hat. Each has a piece of paper in front of them and they have to write down a single colour which is their guess as to which  colour hat they are wearing. If anyone gets it right then everyone goes free, otherwise they are all killed. As always, the prisoners are told the situation beforehand and they are given an opportunity to discuss a strategy.

How can the prisoners guarantee success? You might want to start with fewer colours and build up to a general solution. Answer below.

...

Before you see the answer, you should really try the two person case.

Answer: Label each person from 0 to 6 and assign ROYGBIV to 0 to 6 as well. Each person finds the sum of the hats that they can see and then works out what number they would have to add to the sum in order to get their personal number mod 7. (If you haven't seen mod before, I mean what remainder would you get if you divided the number by seven.) Whatever the number is that you have to add is what you convert back into a colour to guess. This guarantees success.

For example, let's say the seven prisoners are wearing ROGBRIG. Their sums of what they can see are [16,15,13,12,16,11,13]. They need to guess the numbers which, when added to these sums, give 0 more than a multiple of 7, 1 more than a multiple of 7, up to... 6 more than a multiple of 7. So in turn they guess [5,0,3,5,2,1,0] which corresponds to IRGIYOR of which the third person guesses correctly.

This method guarantees that all seven possibilities are covered by making sure everyone is just out of sync. A similar method works for n different colours worn by n prisoners.