Problem

Source: Saint Petersburg olympiad 2024, 11.7

Tags: combinatorics



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?