Problem

Source: 2022 Israel National Olympiad P7

Tags: combinatorics, Info



Gandalf (the wizard) and Bilbo (the assistant) are presenting a magic trick to Nitzan (the audience). While Gandalf leaves the room, Nitzan chooses a number $1\leq x\leq 2^{2022}$ and shows it to Bilbo. Now bilbo writes on the board a long row of $N$ digits, each of which is $0$ or $1$. After this Nitzan can, if he wishes, switch the order of two consecutive digits in the row, but only once. Then Gandalf returns to the room, looks at the row, and guesses the number $x$. Can Bilbo and Gandalf come up with a strategy that allows Gandalf to guess $x$ correctly no matter how Nitzan acts, if a) $N=2500$? b) $N=2030$? c) $N=2040$?