3. The guard suggests the following game to the prisoners. They will all be taken to the courtyard, where each of them will have a hat placed on their head in one of 5 possible colors. The guard will then line them up so that each prisoner can see all the hats except their own, and ask the first prisoner in line whether they know the color of their hat. The prisoner will answer "yes" or "no" out loud. If they answer "no," they will be immediately locked in solitary confinement. If they answer "yes," the guard will ask them what color their hat is, to which the prisoner must respond in such a way that the other prisoners do not hear the answer. If the answer is incorrect, that prisoner will be immediately locked in solitary confinement in front of everyone, and if the answer is correct, that prisoner will be immediately released in front of everyone. The guard then moves on to the next prisoner in line and repeats the same procedure, and so on until the last prisoner. The prisoners have the opportunity to devise a strategy before the game begins, but once the game starts, no communication between prisoners is allowed. If there are 2015 prisoners in the prison, what is the maximum number of prisoners who will be guaranteed to be released if the prisoners apply the optimal strategy?

(Bojan Bašić)

Time for work 270 minutes.

Solutions to the problems should be explained in detail.

Each problem is worth 7 points.

## Ministry of Education, Science and Technological Development Mathematical Society of Serbia
3. Assign values $0,1,2,3,4$ to the colors and let $B$ be the color of the second prisoner's hat, and $S$ be the sum of the colors of the hats from the third to the last prisoner modulo 5. We will describe a strategy for the first two prisoners such that all the others will know $S$, and thus, knowing the colors of the other hats, they can determine their own. This way, freedom will be guaranteed for at least 2013 prisoners. The first prisoner answers "no" if $S \in \{0, B, B+1\}$ or $(B, S) = (4,1)$. In response, the second prisoner answers "no" if $S=0$, and otherwise says "yes" and gives the answer $S$ to the guard. In this way, if two "no" answers are heard, the others know that $S=0$. If the second prisoner says "yes" and is freed, the others know that $S=B$, while if not, they know that $S=B+1$ if $B \neq 4$, or $S=1$ if $B=4$.

In all other cases, the first prisoner says "yes" (it doesn't matter what happens to him). In response, the second prisoner says "yes" if $S \in \{2,4\}$ and gives the answer $S-2$ to the guard. If $B=0$, then $S \notin \{0,1\}$, so the others know that $S=2$ if the second prisoner is freed, $S=3$ if he says "no", and $S=4$ if he says "yes" and misses. Finally, if $B \neq 0$, given the affirmative response of the first, $S \equiv B+2$ or $S \equiv B+3 \pmod{4}$, and the response of the second determines the parity of $S$, allowing the others to determine $S$.

It remains to prove that no strategy guarantees the freedom of 2014 prisoners. Suppose such a strategy exists and consider a set of five arrangements that differ only in the color of the second prisoner's hat. In at most one of these arrangements, the strategy dictates that the first prisoner says "no" (otherwise, the second would not be able to determine the color of his hat with certainty). In at least three of the remaining four arrangements, the first would have to miss, so the second would not be able to determine the color of his hat. This completes the proof.