The king assembled 300 wizards and gave them the following challenge. For this challenge, 25 colors can be used, and they are known to the wizards. Each of the wizards receives a hat of one of those 25 colors. If for each color the number of used hats would be written down then all these number would be different, and the wizards know this. Each wizard sees what hat was given to each other wizard but does not see his own hat. Simultaneously each wizard reports the color of his own hat. Is it possible for the wizards to coordinate their actions beforehand so that at least 150 of them would report correctly?
Problem
Source:
Tags: combinatorics
16.05.2022 15:41
The answer is yes. We will provide a strategy so that exactly $150$ wizards will report correctly. Let $c_0,c_1,\ldots,c_{24}$ be the colors. For $i=0,1,\ldots,24$, let $a_i$ be the number of hats with color $c_i$. It is known to the wizards that $a_0,a_1,\ldots,a_{24}$ are distinct nonnegative integers, hence $$300=\sum_{i=0}^{24}a_i\ge\sum_{i=0}^{24}i=\frac{24\cdot 25}{2}=300.$$Since equality holds, it follows that $a_0,a_1,\ldots,a_{24}$ is a permutation of $0,1,\ldots,24$. We will show that each wizard has exactly two possibilities of his hat's color, one possibility leads to an even permutation and the other possibility leads to an odd permutation. Consider a wisard $W$, and assume he wears a hat with color $c_p$, where $0\le p\le 24$. Hence $a_p\ge 1$ and for each $i=0,1,\ldots,24$, $W$ sees exactly $a_i$ hats with color $c_i$ if $i\ne p$ and also sees $a_p-1$ hats with color $c_p$. There exists a unique integer $q\in[0,24]$ such that $a_q=a_p-1$. In order for $a_0,a_1,\ldots,a_{24}$ to be distinct, the hat $W$ wears must be of color $c_p$ or $c_q$. The two guesses differ in a single swap, so they lead to permutations of different parities. This way, we can divide the wizards beforehand into two disjoint groups of $150$ wizards each. The first group will guess an odd permutation and the second group will guess an even permutation. Therefore exactly $150$ wizards will make a correct guess.
08.01.2024 20:35
Here is a different solution, which doesn't give an explicit strategy: To begin with, note that the minimum possible sum of 25 distinct non-negative integers is 300, which is achieved by adding the numbers from 0 to 24. Therefore, the number of hats of each color must be a permutation of 0 to 24. We define a state as a configuration of hats that meets the conditions. Let's consider the current state from the perspective of one of the wizards. He can see all hats except for one, so the number of hats of each color he can see must be 1, 2,... k, k, k+1,... 24 for some positive integer k, and he knows that his hat color is one of the two colors that have appeared exactly k times. Therefore, he knows he must be in one of two states. Now let's create a graph, with its vertices being all possible states and two vertices sharing an edge if and only if there is some wizard in one of the states that can confuse it for the other state. Notice that this condition is symmetric for the two vertices and that the degree of each vertex is 300, as every wizard confuses the current state with exactly one other state. When a wizard needs to choose between two states, we can look at the corresponding edge in the graph and direct it toward the state he chooses to believe he is in. Therefore, a strategy for the wizards is equivalent to directing all edges in the graph - each wizard looks at the graph, realizes between which two states he needs to choose, and chooses the state according to how we directed the graph. Furthermore, the number of wizards who guess correctly in a given state is equal to the indegree of this state, i.e. to find a strategy that satisfies the conditions we need to direct the edges in the graph such that each vertex will have an indegree of at least 150. In other words, we need to direct the edges in the graph such that the indegree of each vertex will be greater than or equal to the outdegree. The degrees of all vertices are even so we can take an euler cycle in each connected component and direct the edges according to the cycle. In this way, we get that the indegree of each vertex is equal to its outdegree which is what we wanted.