3. A guard proposes the following game to the prisoners. All prisoners are to be taken to the prison yard, where each of them will be put a hat in one of 5 possible colors onto his head, and aligned so that each of them can see all hats but his own. The guard will then ask the first prisoner to say aloud whether he knows the color of his hat. If he answers "no", he will be publicly executed. Otherwise, he will be asked to say the color of his hat in such a way that others do not hear his answer. If the answer is correct, he will be freed, otherwise he will be publicly executed. The guard will then go on to the next prisoner in line and repeat the procedure, and so on. The prisoners may devise a strategy before the game starts, but no communication between them during the game is allowed. If there are 2015 prisoners, what is the maximal number of them that can have guaranteed freedom using an optimal strategy?

(Bojan Bašić)

Time allowed: 270 minutes. Each problem is worth 7 points.

Belgrade, 28.03.2015.

## Second Day
3. Denote the colors by numbers $0,1,2,3,4$. Let $B$ be the color of the second prisoner's hat and let $S$ be the sum modulo 5 of hat colors of all prisoners but the first two. We shall describe a strategy of the first two prisoners which lets all the others know $S$, which will in turn determine their own hat color. Thus (at least) 2013 prisoners will be released.

The first prisoner answers No if $S \in\{0, B, B+1\}$ or $(B, S)=(4,1)$. The second prisoner then answers No if $S=0$ and answers Yes followed by the guess $S$ otherwise. In this way, if both answers are No, the others can deduce $S=0$. Also, if the second prisoner is released, they deduce $S=B$, whereas if he answers Yes and dies, they deduce $S=B+1$ (if $B \neq 4$ ) or $S=1$ (if $B=4$ ).

Suppose the first prisoner answers Yes instead (his fate does not matter). The second then answers Yes if $S \in\{2,4\}$ and guesses $S-2$. Then $B=0$ would imply $S \notin\{0,1\}$, so the others would know that $S=2$ if the second prisoner is set free, $S=3$ if he says $N o$, and $S=4$ if he says Yes and misses. Finally, if $B \neq 0$, since
the first answered in the affirmative, we have $S \equiv B+2$ or $S \equiv B+3(\bmod 4)$, and the answer of the second determines the parity of $S$ and $S$ itself.

It remains to show that no strategy can guarantee freedom for 2014 prisoners. Suppose that such a strategy exists and consider five configurations differing in the second prisoner's hat color only. The first can say No in at most one case (otherwise the second will not be able to determine his hat color), and in at least three of the remaining four cases the first would have to miss, leaving the second with insufficient data again. The proof is complete.