# Where is the theory about "binary toggling games"?

Let us -- using parameters $$M, N$$ and $$L$$ --

1. create an ordered set of size $$M$$ of $$N$$-bit long vectors $$V$$ and initialize them randomly: $$V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in \{0\ ..\ N-1\}, \forall k \in \{0\ ..\ M-1\}$$.

2. create an N-bit long vector $$A_0$$ and initialize it to ones.

3. create an $$M$$-bit long vector $$S$$ and initialize it randomly in the same manner as any $$V_k$$.

4. for $$i$$ from $$0$$ to $$M$$, if $$S[i] = 1$$, then $$A_i = A_{i-1} \oplus V_i$$, otherwise $$A_i = A_{i-1}$$, resulting in $$A_M$$ after $$M$$ steps

5. present an agent/player with $$A_M$$ together with all vectors $$V_k$$ and make him return $$S$$ or the set of indices of vector $$S$$ where $$S[i] = 1$$. It follows that $$A_M \oplus V_{i_0} \oplus V_{i_1} \oplus V_{i_2} \oplus\ ...\ \oplus V_{i_{last}} = A_0$$.

A simple example with $$N=4$$ and $$M=3$$:

$$A_M = [0, 1, 0, 1]$$, $$V_0 = [1, 1, 0, 1]$$, $$V_1 = [0, 0, 1, 1]$$, $$V_2 = [0, 1, 1, 1]$$

solution $$\rightarrow S = [1, 0, 1],$$ because $$A_M \oplus V_0 \oplus V_2 = [1, 1, 1, 1]$$

This problem occurs in many games I have encountered and never really gave it much thought, until now. For the purpose of this question, I have called it the "binary toggling game".

What I wonder is:

• what are "binary toggling games" really called
• what is the theory being them: algorithms, their complexity (classes), edge cases, etc.

• I'm not exactly sure what you're describing here. Are you simply asking about the problem of finding indices s.t. the equation in point 5 holds? The lights out puzzle seems to be a special case of this problem. Jun 2 '20 at 14:52
• @Discretelizard yes, the lights out is definitely a special case of this problem, thanks for finding out. I have expected this problem to have a general name, since I've encountered many of its variants, like the lights out puzzle. Jun 2 '20 at 18:23

"Binary toggling games" are generally just arithmetic problems over GF(2).

Your particular problem is equivalent to the following over GF(2):

$$\sum_i V_iS_i = 1 + A_M$$

If we write $$\vec{S} = [S_1, S_2, \dots]^T$$ and $$V = [V_1, V_2, \dots]^T$$ we find that your problem is actually a simple matrix equation over GF(2): $$V\vec{S} = 1 + A_M$$

You can solve this problem using Gaussian elimination over GF(2). In your example:

$$\left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 0 \end{array}\right) \longrightarrow \left(\begin{array}{ccc|c@} \color{red}1 & 0 & 0 & 1\\ 0 & 0 & 1 & 1\\ 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 \end{array}\right)\longrightarrow \left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 0 &\color{red}1 & 1 & 1\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 0 \end{array}\right)\longrightarrow \left(\begin{array}{ccc|c@} 1 & 0 & 0 & 1\\ 0 &1 & 0 & 0\\ 0 & 0 & \color{red}1 & 1\\ 0 & 0 & 0 & 0 \end{array}\right)$$

From which we can read off that $$S_1 = 1$$, $$S_2 = 0$$ and $$S_3 = 1$$.

• Thank you for the clarification. Jun 2 '20 at 18:29