1
$\begingroup$

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_k$, 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.

Could you please provide links? I hope they exist.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Discrete lizard Jun 2 '20 at 14:52
  • $\begingroup$ @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. $\endgroup$ – Captain Trojan Jun 2 '20 at 18:23
2
$\begingroup$

"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$.

$\endgroup$
1
  • $\begingroup$ Thank you for the clarification. $\endgroup$ – Captain Trojan Jun 2 '20 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.