Mitranov I.V.

The King decided to reward a group of $n$ sages. They will be placed in a row, all facing the same direction, and a black or white hat will be placed on each of them. Each sage will see the hats of all those in front of them. The sages will take turns, from the last to the first, naming a color (white or black) and a natural number of their choice. At the end, the number of sages who named the color matching their own hat will be counted: the group will receive a bonus for exactly that many days. The sages are allowed to agree in advance on how to answer. However, the sages know that exactly $k$ of them are insane (who exactly is unknown to them). An insane sage will name a white or black color and a number regardless of the agreement. What is the maximum number of days with a bonus that the sages can guarantee for the group, regardless of the position of the insane in the queue?
Evaluation. $ $\$$ Madmen, obviously, may not guess correctly. The first speaking wise man can also not guess correctly, as he has no information about the color of his hat. Therefore, more than $\$ n-\mathrm{k}-1$ \$ correct guesses cannot be guaranteed.

Algorithm. Let all the wise men uniformly encode the coloring of the hats they see. A wise man seeing $\$ \$ \$$ hats calls out a number from $\$ 1$ to \$2^і. Then, each wise man, except the first one, is informed of the color of his hat by all previous speakers. The question is only who among them to listen to in order to name his own color.

Let's call the first speaker the current oracle. The strategy of a wise man is to call out the color indicated by the last oracle. If the speaker listens to the oracle, then he himself becomes the oracle; otherwise, the oracle does not change. Since everyone hears everything, each can track who the current oracle is.

Note that each of the wise men will be an oracle. Each wise man, except the last one speaking among them, will be listened to by someone on the segment up to and including the next wise man. Therefore, there will be at least $\$ n-\mathrm{k}-1 \$$ correct guesses.

## Answer

$\$ n-\mathrm{k}-1 \$$.
