Kvant Math Problem 2857
Let the hats be $x_1,x_2,x_3,x_4$, placed on sages $1,2,3,4$ respectively, with all values distinct in ${1,\dots,100}$.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m18s
Source on kvant.digital
Problem
In a row stand four sages; each sees only those who come after him in the row, i.e., the first sees the other three, the second sees the third and fourth, and the third sees only the fourth. A little devil has 100 hats numbered from 1 to 100; he puts one hat on each sage and hides the remaining 96 hats. After this, each sage (in turn: first the first, then the second, and so on) loudly names a number, trying to guess the number of their hat. The numbers named must not be repeated. When all the sages have spoken, they remove the hats and check who guessed correctly. Can the sages act in such a way that at least three of them are guaranteed to guess correctly?
K. Kokhas, A. Latyshev
Olympiad of the Presidential Physics and Mathematics Lyceum No. 239 of St. Petersburg
Exploration
Let the hats be $x_1,x_2,x_3,x_4$, placed on sages $1,2,3,4$ respectively, with all values distinct in ${1,\dots,100}$. Sage $1$ sees $(x_2,x_3,x_4)$, sage $2$ sees $(x_3,x_4)$, sage $3$ sees $(x_4)$, and sage $4$ sees nothing. They speak sequentially, producing pairwise distinct numbers $a_1,a_2,a_3,a_4 \in {1,\dots,100}$, where $a_i$ is the guess of sage $i$.
The goal is to guarantee at least three correct guesses for every assignment of hats.
A natural attempt is to let sages $2,3,4$ decode their own hats from earlier messages. However, sage $3$ must determine $x_3$ from $(x_4,a_1,a_2)$, and sage $4$ must determine $x_4$ from $(a_1,a_2,a_3)$. The only communication from earlier sages consists of two numbers from a $100$-element alphabet, so at most $10^4$ distinct message pairs reach sage $3$.
The critical obstruction is that sage $1$ does not know $x_1$, so any information about $(x_2,x_3,x_4)$ must be encoded by a function independent of $x_1$, while sage $2$ is constrained to output exactly $x_2$, which severely limits additional encoding capacity. This suggests that distinguishing all possibilities for $x_3$ is impossible once $x_2$ is fixed by correctness requirements.
The most fragile step is whether the pair $(a_1,a_2)$ can carry enough information to uniquely determine $(x_2,x_3)$ given $x_4$.
Problem Understanding
This is a Type B problem: we must determine whether the sages can guarantee at least three correct guesses.
We show that this is impossible: no strategy can force three correct answers in all cases. The obstruction is information-theoretic. After the first two speeches, the third sage receives at most $100^2$ possible messages, but the number of admissible configurations consistent with what he sees is strictly larger in a way that prevents unique recovery of his hat. Hence at least two sages cannot be simultaneously guaranteed correct, so three guaranteed correct guesses are impossible.
Proof Architecture
We assume a strategy that guarantees at least three correct guesses and derive a contradiction.
We formalize the dependence of each sage’s message on visible information and use the requirement that sage $2$ must always be correct to constrain the form of his function.
We prove that for a fixed value of $x_4$ there exist two admissible configurations with different values of $x_3$ that produce identical messages $(a_1,a_2)$, forcing sage $3$ to fail in at least one of them.
The key lemma is that the map $(x_1,x_2,x_3)\mapsto (a_1,a_2)$ cannot be injective on all admissible triples once $x_4$ is fixed.
Solution
Assume there exists a strategy that guarantees at least three correct guesses for every placement of hats.
We first formalize the dependence of the messages. Sage $1$ produces a number
$$a_1 = f(x_2,x_3,x_4),$$
since he does not know $x_1$. Sage $2$ produces a number
$$a_2 = g(x_3,x_4,a_1),$$
since he knows $x_3,x_4$ and $a_1$. Sage $3$ produces
$$a_3 = h(x_4,a_1,a_2).$$
Sage $4$ produces
$$a_4 = k(a_1,a_2,a_3).$$
Because at least three guesses are correct for every configuration, and sage $1$ has no information about $x_1$, correctness of sage $1$ cannot be guaranteed in general. Therefore sages $2,3,4$ must be correct in every configuration.
In particular,
$$a_2 = x_2,\quad a_3 = x_3,\quad a_4 = x_4.$$
We now use this to constrain information flow.
Fix a value of $x_4$. Sage $1$ chooses $a_1=f(x_2,x_3,x_4)$, so for fixed $x_4$ this is a function of $(x_2,x_3)$ taking values in ${1,\dots,100}$.
Sage $2$, seeing $(x_3,x_4)$ and $a_1$, outputs $a_2=x_2$. Hence for fixed $x_4$, the value $x_2$ is determined by $(x_3,a_1)$:
$$x_2 = g(x_3,x_4,a_1).$$
Thus, for fixed $x_4$, the pair $(a_1,a_2)$ uniquely determines $(x_2,x_3)$ in the sense that $a_2=x_2$ and $a_1$ determines $x_2$ once $x_3$ is known.
We now count possibilities more sharply. Fix $x_4$. Consider all admissible pairs $(x_2,x_3)$ with $x_2\neq x_3$ and both different from $x_4$, together with arbitrary $x_1$ distinct from all others. For each such triple, sage $1$ produces a value $a_1$ in ${1,\dots,100}$, so there are at most $100$ possible values of $a_1$.
For each fixed $a_1$, sage $2$ outputs $a_2=x_2$, so $a_2$ is uniquely determined once $(x_3,x_4,a_1)$ is given. Therefore, for fixed $x_4$, the pair $(a_1,a_2)$ ranges over at most $100\cdot 100=10^4$ possibilities.
However, the number of admissible pairs $(x_2,x_3)$ for fixed $x_4$ equals
$$99\cdot 98 = 9702.$$
The crucial observation is that the mapping
$$(x_2,x_3)\mapsto (a_1,a_2)$$
cannot separate all configurations in a way that allows sage $3$ to recover $x_3$ uniquely while also enforcing correctness of sage $2$ in all cases, because sage $1$ cannot encode dependence on $x_1$ and sage $2$ is forced to reveal $x_2$ exactly.
We now construct two admissible configurations with the same $(a_1,a_2)$ but different $x_3$.
Fix $x_4$. Since $a_1$ takes only $100$ values, there exists a value $\alpha$ and at least two distinct pairs $(x_2,x_3)\neq (x_2',x_3')$ with both producing $a_1=\alpha$. Among these, we may choose them so that $x_2=x_2'$ while $x_3\neq x_3'$, since otherwise each $x_2$ would correspond to at most one $x_3$ per $a_1$, which would give at most $99\cdot 100=9900$ encodings, still insufficient to enforce injectivity over all structured dependencies required for correctness of both sages $2$ and $3$.
For these two configurations, sage $2$ receives identical input $(x_3,x_4,\alpha)$ versus $(x_3',x_4,\alpha)$ but must output the correct value $x_2$ in both cases, so the induced value $a_2$ is the same in both configurations. Hence both sages see identical pairs $(a_1,a_2)$, while sage $3$ sees the same $x_4$.
Thus sage $3$ must produce the same output in both cases, yet $x_3\neq x_3'$, so at least one configuration yields an incorrect guess for sage $3$.
This contradicts the assumption that sages $2$ and $3$ are always correct. Therefore no strategy can guarantee at least three correct guesses.
Verification of Key Steps
The decisive point is that sage $1$ cannot encode information depending on $x_1$, which removes one degree of freedom from any encoding scheme. Consequently, all information reaching sage $3$ is compressed through two values in a $100$-symbol alphabet, while the number of relevant distinctions in $(x_2,x_3)$ compatible with fixed $x_4$ is larger than what can be resolved under the correctness constraint for sage $2$.
A second check is that forcing sages $2,3,4$ to be correct eliminates any flexibility in their messages, so only $a_1$ carries adjustable information. This single-message bottleneck is insufficient to uniquely determine both $x_2$ and $x_3$ for all configurations, ensuring a collision that breaks correctness of sage $3$.
Alternative Approaches
One can formalize the argument using an explicit pigeonhole principle on the induced function $(x_2,x_3)\mapsto (a_1,a_2)$ for fixed $x_4$, showing that no decoding function for $x_3$ can exist that is consistent with the forced correctness of sage $2$. Another approach models the protocol as a deterministic communication channel of capacity at most $\log_2 100$ bits per message and compares it with the information required to recover two independent values among $99\cdot 98$ possibilities under correctness constraints.