5. The power in the kingdom of gnomes was seized by giants. The giants decided to get rid of the gnomes and told them the following: "Tomorrow we will line you up so that each of you will see those who stand after and not see those who stand before (i.e., the 1st sees everyone, the last sees no one). We will put either a black or a white hat on each of you (equally likely, each will have either a black or a white hat) and ask what color it is. Those who answer correctly will be released, and those who answer incorrectly will be executed." How many gnomes can be risked at a minimum with certain agreements before the execution, if there are p gnomes in the kingdom and p $<\infty$. Justify your answer. (12 points)

#
# Solution:

The gnomes agree as follows: they risk the first gnome, telling him the following: "Denote a white hat as 1 and a black hat as 0, and count the sum of the remaining n-1 gnomes. If the sum is even, say 'white'; if it is odd, say 'black'. Under this condition, the first gnome dies with a probability of $1 / 2$. The second gnome counts the sum of the (n-2) gnomes. If the sum has changed, it means he has a white hat. The others hear him and adjust the parity of the remaining gnomes, and so on. Answer: 1 gnome.

Answer: 1.

| Points | Criteria for evaluating the completion of task № 5 |
| :---: | :---: |
| 12 | A correct and justified sequence of all steps of the solution is provided. The correct answer is obtained. |
| 10 | A correct sequence of all steps of the solution is provided. There are gaps in the justification of the parity of the sum, but they do not affect the further course of the solution. |
| 8 | The problem is not solved, but its solution is significantly advanced, i.e.:  - a significant part of the solution is performed correctly, possibly inaccurately (for example, it is proposed to denote a white hat as 1 and a black hat as 0);  - another part is either not performed or performed incorrectly, possibly even with logical errors (for example, the necessity of adjusting the parity of the sum is not proven).  The solution may be incomplete. |
| 5 | The problem is not solved, but there is some progress in its solution, i.e.:  - the initial part of the solution is performed correctly (for example, the assumption about the probable death of the first gnome is correctly stated or the cases of even and odd numbers of gnomes are considered);  - the main part is either not performed or performed incorrectly, possibly even with logical errors (for example, the correspondence between the color of the hat and the numbers is not shown, or the probability of the first gnome's death is insufficiently justified, or an incorrect conclusion is drawn from the parity and non-parity of the number of gnomes, or the assumption is made that the gnomes can exchange additional information or that execution occurs immediately upon an incorrect answer and the others see it).  The solution may be incomplete. |
| $\mathbf{0}$ | All cases of the solution that do not meet the criteria for scoring 5, 8, 10, and 12 points. |