6. The Sultan gathered 300 court wise men and proposed a test. There are 25 different colors of hats, known in advance to the wise men. The Sultan informed them that one of these hats would be placed on each of the wise men, and if the number of hats of each color is written down, all the numbers will be different. Each wise man will see the hats of the others, but not his own. Then all the wise men will simultaneously announce the supposed color of their own hat. Can the wise men agree in advance to act in such a way that at least 150 of them will definitely name the correct color?
(A. V. Grialko) Solution. Since $0+1+2+\ldots+24=300$, the quantities of caps of different colors take all values from 0 to 24.

Next, each sage counts the number of caps of each color. For two colors, the quantities of caps coincide, and the sage understands that he is wearing a cap of one of these two colors. It only remains to choose which of these two colors to name.

There are various ways to agree (in advance!) on how each sage should make this choice. For example, a regular bipartite graph can be constructed and Hall's lemma for Arab countries can be used. The strategy presented below is based on the concept of the parity of a permutation.

Let the sages pre-number the colors with numbers from 0 to 24. Then the true distribution of caps corresponds to the permutation

$$
\begin{gathered}
\text { color number } \\
\text { number of caps }
\end{gathered}\left(\begin{array}{ccccccccc}
0 & 1 & 2 & \ldots & i & \ldots & j & \ldots & 24 \\
a_{0} & a_{1} & a_{2} & \ldots & a_{i} & \ldots & a_{j} & \ldots & a_{24}
\end{array}\right)
$$

If a sage sees an equal number of caps of color $i$ and color $j$ (with $k$ caps of each of these two colors), then he needs to decide which of these two colors to attribute his cap to, that is, to choose between two permutations

$$
\left(\begin{array}{ccccccccc}
0 & 1 & 2 & \ldots & i & \ldots & j & \ldots & 24 \\
a_{0} & a_{1} & a_{2} & \ldots & k & \ldots & k+1 & \ldots & a_{24}
\end{array}\right) \quad\left(\begin{array}{ccccccccc}
0 & 1 & 2 & \ldots & i & \ldots & j & \ldots & 24 \\
a_{0} & a_{1} & a_{2} & \ldots & k+1 & \ldots & k & \ldots & a_{24}
\end{array}\right) .
$$

One of these permutations corresponds to the true distribution of colors, and the specified permutations differ in the placement of exactly two elements, so they have different parities.

The sages can agree in advance that exactly 150 of them will make their choice in favor of the even permutation, and the other 150 will choose the odd permutation.

Then exactly half of the sages will correctly name the color of their cap.

Remark. The strategy according to which the sages agree in advance that 150 of them choose the color with the higher number (of the two between which they need to choose), and the other 150 choose the color with the lower number, does not guarantee 150 correct answers.

Indeed, let the true distribution of caps correspond to the permutation

$$
\begin{gathered}
\text { color number } \\
\text { number of caps }
\end{gathered}\left(\begin{array}{llllllllllllll}
0 & 1 & 2 & \ldots & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\
0 & 1 & 2 & \ldots & 15 & 16 & 17 & 24 & 23 & 22 & 21 & 20 & 19 & 18
\end{array}\right)
$$

and let the sages who received caps of colors 3-17 (exactly 150 people) choose the color with the lower number, while the other 150 sages choose the color with the higher number. Then all the sages, except for the sages with caps of colors 1, 2, and 24, will name the color incorrectly.