ASeDatAb
This post is about the problem ASeDatAb from round 1B of the 2022 Google Code Jam.
Problem
You are playing a guessing game with an opponent. The opponent starts by picking a secret 8-bit binary string. Then, the game progresses in rounds. Each round, you provide an 8-bit binary string as a guess. The opponent is allowed to rotate your guess to any one of the 8 possibilities (e.g. 11000000 can be rotated to 00110000). Then, the opponent computes the XOR of the rotated guess and their secret string, and uses the result as their new secret. At any point, if the opponent's secret is 00000000, then you win! Apart from letting you know if you've won though, the opponent does not reveal any other information. They don't tell you how much they rotated your guesses, or what the value of their secret is at any point (unless all the bits are zero because that means you have won). How can you guarantee victory?
Solution
We can generalize this game to \(2^k\) bits. We will show that for all \(k\), there exists a sequence of guesses that will guarantee victory. We will construct such a sequence \(P_k\) via induction. In the base case where \(k = 0\), \(P_0 = [1]\) will guarantee victory. To see why, observe that either the secret string starts off as a 0 or a 1. If it starts off as 0 then you have already won, and if it starts off as 1 then guessing 1 will cause the opponent to change their string to 0 (since 1 XOR 1 is 0).
Now let's consider the case where \(k = 1\), i.e. there are 2 bits. In this case, either the two bits of the secret string are the same or different. If they are the same, then either it is 00 in which case you have already won, or it is 11 in which case you can guess 11 to force the opponent to change their secret string to 00. However, if they were different to begin with, then they will still be different after you guess 11. Now, you can guess 10 to force the opponent to make the two bits the same (no matter how the guess is rotated, it will flip one of the bits to make both the same). Finally, assuming you haven't won yet, then the secret must be 11 so you can guess 11 again. So \(P_1 = [11, 10, 11]\) guarantees victory.
We can generalize the above approach to construct \(P_{k+1}\) inductively given \(P_{k}\). First we will introduce some definitions. Let \(PP_{k}\) represent the sequence formed by concatenating each string in \(P_{k}\) with itself, e.g. \(PP_{1} = [1111, 1010, 1111]\). Let \(P0_{k}\) represent the sequence formed by padding each string in \(P_{k}\) with \(2^{k}\) zeroes, e.g. \(P0_{1} = [1100, 1000, 1100]\). Finally, let \(N_k\) be the number of elements in \(P_k\). Given these definitions, we construct \(P_{k+1}\) to be \(N_k + 1\) copies of \(PP_{k}\) interspersed between the elements of \(P0_{k}\). For example: \[P_2 = PP_1 + [1100] + PP_1 + [1000] + PP_1 + [1100] + PP_1\] \[ = [1111, 1010, 1111, \textbf{1100}, 1111, 1010, 1111, \textbf{1000}, \\ 1111, 1010, 1111, \textbf{1100}, 1111, 1010, 1111] \]
I won't write out \(P_3\) because it's very long, but it has \(N_3 = N_2 * (2 + N_2) = 255\) elements. If you guessed each of the strings in \(P_3\) in order for the original game with 8 bits, you're guaranteed to win! 255 is the upper bound for the number of guesses you'll need to make, but it's possible you win sooner depending on the initial secret and the opponent's choice of rotations.
We will break down the proof that this construction for \(P_{k+1}\) works into two parts. First, we will show that if the left \(2^{k}\) bits of the secret equal the right \(2^{k}\) bits, then guessing \(PP_{k}\) will lead to victory. Then, we will show that it's guaranteed the left and right halves of the secret will indeed be the same before one of the \(PP_{k}\) blocks in the construction, i.e. either at the beginning, or immediately after one of the elements of \(P0_{k}\).
Lemma 1: If the left \(2^{k}\) bits of the secret equal the right \(2^{k}\) bits, then guessing \(PP_{k}\) will lead to victory
To prove this, recall that each element of \(PP_{k}\) is an element of \(P_k\) concatenated to itself. The crucial observation is that rotating an element of \(PP_{k}\) is equivalent to rotating the corresponding element of \(P_k\) before concatenating it with itself. To see why, let's represent an element of \(P_k\) as \(aXz\), where \(a\) and \(z\) are the first and last bits respectively and \(X\) is all the bits in between. Then, the the corresponding element of \(PP_k\) is \(aXzaXz\). Rotating this string once results in \(zaXzaX\), and rotating the substring \(aXz\) once before concatenating it to itself also results in \(zaXzaX\), which proves the crucial observation.
A corollary of this observation which we will use in Lemma 2 is that if we rotate an element of \(PP_{k}\), the left and right halves will still be equal.
This observation implies that guessing the sequence \(PP_k\) is equivalent to guessing \(P_k\) on each of the halves of the secret. By our inductive hypothesis, we know that guessing \(P_k\) will make each half of the secret contain all zeroes. If the two halves of the secret are the same, they will both become all zeroes at the same time, so this proves that guessing \(PP_k\) will lead to victory if the two halves of the secret are the same.
Lemma 2: It's guaranteed the left and right halves of the secret will be the same before one of the \(PP_{k}\) blocks in the construction
To prove this, we will look at the value of the left half of the secret XOR'd with the right half. Let \(\oplus\) represent the XOR operator, and \(L\) and \(R\) represent the left \(2^k\) and right \(2^k\) bits of the secret, respectively. Note that \(L\) and \(R\) do not have a fixed value, but can change as guesses are applied to the secret.
The first crucial observation is that guessing a string in \(PP_{k}\) will not change the value of \(L \oplus R\). We know from the corollary in Lemma 1 that the two halves of the guess will be equal even after rotation. Therefore, we can represent the rotated guess as \(XX\) (where \(X\) is a string with \(2^{k}\) bits). If \(L'\) and \(R'\) are the initial left and right halves of the secret, then the new left and right halves of the secret after the guess will be \(L' \oplus X\) and \(R' \oplus X\) respectively. Now, observe that \[(L' \oplus X) \oplus (R' \oplus X) = L' \oplus R' \oplus X \oplus X \] \[ = L' \oplus R' \oplus 0 \] \[ = L' \oplus R' \] This shows that guessing a string in \(PP_{k}\) does not change the value of \(L \oplus R\).
Now, consider an element of \(P0_{k}\). Let's denote the the left \(2^k\) bits of the element as \(Y\), and the right \(2^k\) bits (which are all \(0\)) as \(Z\). The second crucial observation is that guessing an element of \(P0_{k}\) will cause the value of \(L \oplus R\) to be XOR'd with some rotation of \(Y\). To see why, observe that if we rotate \(YZ\) and then XOR the left half with the right half, each bit of \(Y\) will be paired with a bit in \(Z\). Since all the bits of \(Z\) are zero, taking the XOR of the left and right halves will preserve all the bits of \(Y\), up to some rotation. In other words, if \(L_g\) and \(R_g\) are the left and right halves of the rotated guess, then \(L_g \oplus R_g = Y_r\) where \(Y_r\) is some rotation of \(Y\). Finally, if \(L'\) and \(R'\) are the initial left and right halves of the secret, we see that \[(L' \oplus L_g) \oplus (R' \oplus R_g) = L' \oplus R' \oplus L_g \oplus R_g \] \[ = (L' \oplus R') \oplus Y_r \] Since \(Y\) is an element of \(P_k\), this shows that guessing a string in \(P0_{k}\) changes the value of \(L \oplus R\) by XOR-ing it with a rotation of the corresponding element of \(P_{k}\).
To summarize, \(L \oplus R\) is itself a string with \(2^k\) bits. Elements of \(PP_k\) do not affect it, and elements of \(P0_k\) act on it as if we had guessed the corresponding element of \(P_k\). Therefore, by our inductive hypothesis, all the bits of \(L \oplus R\) will be equal to zero at some point, since that's the definition of \(P_k\)! Finally, note that \(L \oplus R = 0\) implies \(L = R\), so this proves Lemma 2.
Conclusion
Lemma 2 implies that the two halves of the secret will be equal before a \(PP_k\) block, and Lemma 1 implies that applying \(PP_k\) when the two halves of the secret are equal will make all the bits in the secret zero. Therefore, our construction for \(P_{k+1}\) is valid.