A tourist has arrived on an island where $100$ wizards live, each of whom can be a knight or a liar. He knows that at the time of his arrival, one of the hundred wizards is a knight (but does not know who exactly), and the rest are liars. A tourist can choose any two wizards $A$ and $B$ and ask $A$ to spell on $B$ with the spell "Whoosh"!, which changes the essence (turns a knight into a liar, and a liar into a knight). Wizards fulfill the tourist's requests, but if at that moment wizard $A$ is a knight, then the essence of $B$ really changes, and if $A$ is a liar, that doesn't change. The tourist wants to know the essence of at least $k$ wizards at the same time after several consecutive requests. For which maximum $k$ will he be able to achieve his goal?
Problem
Source: Saint Petersburg olympiad 2024, 11.7
Tags: combinatorics
russian_destroyer
25.09.2024 03:38
The answer is $k=1$. We'll work in $\mathbb{F}_2$ and attribute a $1$ to a knight and a $0$ to a liar. Let $x_1, x_2, \ldots, x_{100}$ be the initial numbers of the wizards, exactly one of which is equal to $1$. Then, if wizards $A$ and $B$ have numbers $a$ and $b$ before $A$ casts a spell over $B$, $B$'s number after the spell becomes $a+b$. In general, at each step we choose two wizards, each having their current number expressed as a linear sum of $x_i$, and add the first wizard's current number to the second one's in $\mathbb{F}_2$. It makes sense to store the information as a $100 \times100$ matrix where the number on the $i$-th row and $j$-th column is the scalar of $x_j$ in the number currently attributed to wizard $i$. Observe that an operation is simply adding one row to another. However, our initial matrix is just $I_{100}$, and the determinant is invariant under operations, so it must always be nonzero in $\mathbb{F}_2$. Therefore, no row can ever consist of just zeros and no two rows can have only ones at the same time. But, if a wizard has a row that is not all zeros or all ones, we can't be sure of its $\emph{essence}$, as the $x_i$ which is equal to $1$ could be in its representation or not. Hence, at each point in time, we can for sure know the $\emph{essence}$ of at most one wizard, i.e. $k\leq 1$. To guarantee $k=1$, we can repeatedly add all rows to the first one, thus making sure that after $99$ steps, the first wizard is a liar.
.