Hi everybody,

Here are a few very nice problems about guessing colors of hats, subject to various constraints. All are very quick to state, and have interesting solutions. They may be well known but a quick search on the forum about "hats" gave few answers. One of these problems was just submitted by godelproof in another thread that kept me happily busy tonight...

1) This is the story of N magicians that have been captured by a cannibal (don't ask me how or why). In order to spice things up, this cannibal decides to have the magicians play a game to determine who will eventually be devoured. He gathers his prisonners and explains to them the following rules:

On the next morning, the magicians will have to stand in a long queue, and each of them will be given a coloured hat, either red or blue (any combination is possible). They will be able to see the hats of the people in front of them, but neither those of the people standing behind, nor their own.

Then, one by one, starting with the magician at the tail, the cannibal will ask them for the colour of the hat they're wearing. They will answer loudly, and unbeknowst to the other magicians they will either be freed or killed depending whether the answer was right or wrong. Thus each magician knows the previous answers, but not if they were correct.

During all night, the magicians may prepare a strategy together.

The question is: how many magicians can be saved surely, and how?

NB: the magicians can't provide more information than the very colour they tell to the cannibal. (No accent, no timing,...)

NB2: even though they are magicians, they don't have any supernatural power.

2) What if there are different colours of hats instead?

3) Again with 2 colors. Assume N is even. Suppose now that the magicians will stand around a circle instead of a line, so that they will see the colour of every other hat but their own. This may look like an advantage... However, since there is no natural starting point, the cannibal will ask them to tell their colour all at once (which means in particular that they can't use the answer of the others). Again, is it possible to save magicians surely? If yes, how many?

4) What if N is odd, or if there are more than 2 colors? [n.b.: I don't have the answer for these ones by now]

The last one is hyper hard, but hyper cool... (well, actually it depends on your tastes)

5***) Consider the same problem as 1) but with infinitely many magicians in the queue: there is a last one (who sees every one else) but no first one. We assume furthermore that, like in 3), no information is communicated between magicians: they don't know what the previous ones answered or if they were killed. Although this is clearly impossible, you are asked to prove that there exists a strategy to save all but finitely many magicians. What if there are more colors?

About this last one:

Spoiler:

Enjoy!

Laurent.