![](https://cdn.mathpix.com/cropped/2024_05_06_f68ab0b4ba9161e79ed2g-14.jpg?height=229&width=2041&top_left_y=1598&top_left_x=0)

Authors: Lobanov M. S., Ushakov V. G.

A team of $n$ schoolchildren participates in a game: each of them is given a hat of one of $k$ pre-known colors, and then, at a whistle, all schoolchildren simultaneously choose a scarf for themselves. The team scores as many points as the number of its members whose hat color matches the scarf color (there is a sufficient number of scarves and hats of any color; during the game, each participant cannot see their own hat, but can see the hats of all others, and is not allowed to convey any information until the whistle). What is the maximum number of points the team, having pre-planned the actions of each of its members, can guarantee to get:

a) for $n=k=2$

b) for arbitrary fixed $n$ and $k$?
Note that the actions of each player under any plan are uniquely determined by the colors of the hats of the other team members (since he has no other information).

a) Regardless of the hat color of the first player, after this, the scarf color chosen by the second player is uniquely determined. Since the second player can be given a hat of either color, there will be cases where the scarf and hat colors do not match. Therefore, it is impossible to guarantee two matches. We will show that one match can always be guaranteed.

Let the players agree in advance that the first player chooses a scarf to match the color of the second player's hat, and the second player chooses a scarf to be the opposite color of the first player's hat. Then, if they are given hats of the same color, the scarf and hat colors will match for the first player, and if they are given hats of different colors, they will match for the second player. Therefore, there will always be exactly one match.
b) Suppose the hat colors of all players except the first are fixed, and the first player can have any of the $k$ colors. Since the actions of the first player are uniquely determined by the colors of the hats of the other team members, among these $k$ cases, the scarf and hat colors of the first player will match in exactly one case. Since the hats of $n-1$ players can be put on in $k^{n-1}$ ways, among all $k^{n}$ ways of putting on hats for $n$ players, the scarf and hat colors of the first player will match in exactly $k^{n-1}$ cases. The same is true for any player. Therefore, for any fixed plan of actions, among all $k^{n}$ ways of putting on hats, there will be a total of $n k^{n-1}$ matches of the scarf and hat colors of some players. Thus, the average number of matches per way of putting on hats will be $n k^{n-1} : k^{n} = n / k$, and, consequently, the minimum number of matches does not exceed $n / k$.

We will describe a plan of action for the players that always guarantees $\left[{ }^{n} / k\right]$ matches. We will assign numbers $0,1,2, \ldots, k-1$ to the colors. We will divide the players into $\left[{ }^{n} / k\right]$ groups of $k$ people each (the remaining players can act arbitrarily). In each group, let the players receive different numbers from 0 to $k-1$. During the game, let the $i$-th player choose the scarf color so that the sum of all numbers corresponding to the color of his scarf and the colors of the hats of the other players in his group gives a remainder of $i$ when divided by $k$. In this case, in any situation, exactly one player in the group will guess the color of his hat. Specifically, if the sum of the numbers corresponding to the colors of all the hats of the players in a given group is congruent to $j$ modulo $k$, then the scarf and hat colors will match for the $j$-th player in the group. Therefore, in any case, the scarf and hat colors will match for at least $\left[n^{n} / k\right]$ players.

## Answer

a) 1 ; b) $\left[{ }^{n} / k\right]$

Submit a comment