in the direction), each will be given a black or white hat. Each will see the hats of all those in front of them. The sages will take turns (from the last to the first) to name a color (white or black) and a natural number of their choice. In the end, the number of sages who named the color matching the color of their own hat will be counted: exactly that many days the entire group will be paid a bonus to their salary. The sages were allowed to agree in advance on how to answer. At the same time, 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 agreements. What is the maximum number of days with a bonus to the salary that the sages can guarantee the group, regardless of the location of the insane in the queue?
Evaluation. $k$ madmen obviously cannot guess. The first speaking wise man can also not guess, as he has no information about the color of his hat. Therefore, it is impossible to guarantee more than $n-k-1$ correct guesses.

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 \wedge$ і $\$$. If he calls out a different number, then everyone should consider that he called out one. Then each wise man, except the first speaker, is informed of the color of his hat by all previous speakers. The question is only who to listen to in order to name his color.

Let's call the first speaker the current oracle. The strategy of a wise man is to name 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 speaking one, will be listened to by someone on the segment up to and including the next wise man. Therefore, there will be at least $n-k-1$ correct guesses.

## Answer

$n-k-1$.

Send a comment