2
$\begingroup$

Take any binary vector of length $4n+1$ with $n\geqslant0$. We can activate any bits. When a bit is activated, neighboring bits change their values $0$ -> $1$, $1$ -> $0$. Our goal is to turn the original binary vector into a vector of only ones by activating the bits.

Then I conjecture that if the value of the binary vector belongs to A158705, this is possible for a maximum of $4n+1$ activations. Here A158705 is nonnegative integers with an odd number of even powers of $2$ in their base-$2$ representation.

Similarly for any binary vector of length $4n+3$ with $n\geqslant0$ I conjecture that if the value of the binary vector belongs to A158704, this is possible for a maximum of $4n+3$ activations. Here A158704 is nonnegative integers with an even number of even powers of $2$ in their base-$2$ representation.

Is there a way to prove it?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Of course it is possible with that many activations, why on Earth would you ever activate anything twice? See also mathworld.wolfram.com/LightsOutPuzzle.html $\endgroup$
    – domotorp
    Commented Nov 12, 2021 at 21:11
  • 1
    $\begingroup$ @domotorp It is possible with that many activations only if it is possible at all; if the length is $3k + 2$ (i.e. if $n$ is 1 mod 3), then it may not be possible at all. For example, consider $n = 1$ with the zero-vector. $\endgroup$
    – user44191
    Commented Nov 12, 2021 at 22:14
  • $\begingroup$ @domotorp, thank you for comment! Very interesting link indeed. $\endgroup$
    – Notamathematician
    Commented Nov 13, 2021 at 16:14

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .