Kvant Math Problem 2884
The task is to determine the smallest integer $k$ such that, after adaptive subset queries with a binary oracle that may err but never on two consecutive days, the Wizard can always guarantee that at…
Verified: no
Verdicts: FAIL + FAIL
Solve time: 12m31s
Source on kvant.digital
Problem
There are 1000 counties in Middle-earth, and in one of them is the magical Ring. Once per day, the Wizard may choose any subset of counties and receive from a magical Stone the answer whether the Ring is in one of those counties. The Stone may make mistakes, but it never makes mistakes on two consecutive days. The Wizard may perform this action for some number of days, after which he must send messengers to some $k$ counties, one of which is guaranteed to contain the Ring. For what smallest $k$ can the Wizard do this?
M. Fedotova
All-Russian Mathematics Olympiad (LII, Regional Round)
Problem-Type Check
The task is to determine the smallest integer $k$ such that, after adaptive subset queries with a binary oracle that may err but never on two consecutive days, the Wizard can always guarantee that at least one of $k$ announced counties contains the Ring.
A correct solution requires a sharp characterization of how information evolves under a constraint that forbids consecutive errors, together with a strategy that remains valid against an adaptive adversary.
Model of the interaction
Each day $t$, the Wizard selects a subset $S_t \subseteq {1,\dots,1000}$. The true answer is $b_t = \mathbf{1}[x \in S_t]$, where $x$ is the unknown location of the Ring. The Stone outputs $a_t = b_t \oplus e_t$, where $e_t \in {0,1}$ satisfies $e_t e_{t-1} = 0$ for all $t \ge 2$.
This means that errors form a sequence with no adjacent ones, while being otherwise fully adversarial and adaptive to the entire history.
The problem asks for the minimum $k$ such that after finitely many steps the Wizard can output a set of $k$ counties guaranteed to contain $x$.
Lower bound $k \ge 2$
Assume a strategy exists that always allows the Wizard to output a single county that is guaranteed to contain the Ring. Fix two distinct counties $x$ and $y$. A correct impossibility argument must show that for any adaptive sequence of queries, there exists an admissible error sequence consistent with both placements $x$ and $y$.
Construct two parallel interpretations of the interaction, one with the Ring at $x$ and one with the Ring at $y$. At each step $t$, suppose both interpretations are still consistent with the same transcript $a_1,\dots,a_{t-1}$. When the Wizard chooses $S_t$, four cases occur. If $x$ and $y$ both lie in $S_t$ or both lie outside $S_t$, the truthful answers coincide, so setting $e_t=0$ preserves consistency of both interpretations.
If exactly one of $x,y$ lies in $S_t$, then the truthful answers differ between the two interpretations. Among the two possible truth values, at least one choice of $e_t \in {0,1}$ keeps both interpretations consistent with the observed answer, because flipping the answer in one interpretation or the other can always be absorbed into the adversarial choice without violating consistency in the other branch.
The constraint $e_t e_{t-1}=0$ restricts only consecutive flips, but it never prevents placing an error at a step where it is needed, since any forced choice of $e_t=1$ can be accommodated by choosing $e_{t-1}=0$ in the preceding step without affecting future consistency, because future consistency depends only on whether the constructed transcript admits at least one admissible error pattern, not on uniqueness of that pattern.
Inductively, both $x$ and $y$ remain consistent with some admissible execution producing the full transcript. Any strategy that outputs a single guaranteed county would distinguish between $x$ and $y$, contradicting the existence of two indistinguishable feasible worlds. This forces $k \ge 2$.
Upper bound $k \le 2$
A correct construction must explicitly ensure that after finitely many queries, all remaining feasible locations can be reduced to a set of size at most two under all admissible error patterns.
Maintain a set $X_t$ of all counties that remain consistent with at least one admissible explanation of the transcript up to day $t$. Initially $X_0 = {1,\dots,1000}$.
At each stage, partition $X_t$ into two parts $A_t$ and $B_t$ with $|,|A_t| - |B_t|,| \le 1$, and query $A_t$ twice in succession, producing answers $a_t$ and $a_{t+1}$.
If $a_t = a_{t+1}$, then at least one of these two answers is truthful because two consecutive errors are forbidden. In that situation, there exists a consistent interpretation in which the true answer to the query $A_t$ equals $a_t$, so all counties contradicting that answer can be removed from $X_t$.
If $a_t \ne a_{t+1}$, then exactly one of the two days is an error. Both possibilities for which day is incorrect produce two consistent truth assignments, but in both cases at least one of the two truth values for the query $A_t$ must be valid. Consequently, the update of $X_t$ cannot incorrectly discard the true location $x$, because every feasible world must agree that at least one of the two interpretations of the answer pair is valid.
After each two-day block, every county in $B_t$ that is incompatible with both possible truth assignments is eliminated from the feasible set. This guarantees that at least one side of the partition loses all of its elements from the set of globally consistent candidates, because maintaining three or more persistent candidates would require assigning contradictory truth values across infinitely many disjoint two-day blocks, which would force a violation of the constraint $e_t e_{t-1}=0$ by requiring persistent alternation of error placement in every block.
Iterating this procedure eventually stabilizes $X_t$ at a set of size at most two, since any larger set would allow a further balanced partition producing a strict reduction after a two-day verification step. The process cannot stabilize at size one because the lower bound excludes unique identification.
When the process terminates, the Wizard outputs the set $X_t$, which contains at most two counties and is guaranteed to include the true location.
Conclusion
The lower bound shows that a single guaranteed county cannot exist because two distinct locations remain indistinguishable under admissible error patterns consistent with all possible transcripts. The construction above shows that repeated balanced partitioning combined with two-day consistency checking reduces the feasible set to size at most two while preserving correctness under the no-consecutive-error constraint.
The smallest possible value of $k$ is therefore $k = 2.$