Lightbulb riddle

Question

Suppose you have $n$ lightbulbs evenly distributed over a circle. Each lightbulb can have two states; it's either turned on or turned off. Next to each lightbulb there is a button that changes the state of the $k$ adjacent lightbulbs clockwise (so the button chances the state of the lightbulb next to the button and the following $k-1$ lightbulbs). Implicitly I'll always assume $k<n$. In the beginning, all lightbulbs are switched off.

I'm trying to solve the following two questions (on which I have some thoughts):

1. For which values of $k$ and $n$ can you reach a state where all lightbulbs are on?
2. Given $k$ and $n$ (such that you can reach said state), what is the minimal amount of button pushes required to turn on all lights?

Okay, let's start with some relatively easy insights.

1. If $k$ is odd, you can always turn all lights on by simply pressing all buttons. Indeed, consider any lightbulb. The state of this lightbulb can only be affected by $k$ buttons, if all of these are pressed, the state of the lightbulb changes $k$ times and thus the lightbulb is on as $k$ is odd.
2. If $k$ is even and $n$ is odd, it's impossible to simultaneously turn on all lightbulbs. Indeed, with each press of a button, the parity of the amount of lightbulbs being on does not change (Say that a lightbulb being on gets value 1 and being off gets value 0, pressing a button will swap zeroes to ones and vice-versa. If a button affects an even numbers of states, then modulo 2 the amount nevers changes). It's clear that amount of glowing lightbulbs is zero in the beginning and if all lightbulbs would be glowing, the amount of glowing lightbulbs modulo 2 would be 1. You can never reach that state as each press of a button preserves the parity.
3. For what it's worth, the amount of glowing lightbulbs modulo $k$ is always of the form $2l \mod k$ for some $l$. Indeed, consider a group of $k$ lightbulbs and say $l$ lightbulbs are glowing in this group and thus $k-l$ are off. After the button affecting this entire group, there are $k-l$ lightbulbs glowing and $l$ off. The change in the amount of lightbulbs being on is $l-(k-l)=k+2l$, modulo $k$, the amount of glowing lightbulbs (modulo k) changed by $2l$.

Now let's state something a bit more involved. Suppose that $n$ and $k$ have a common divisor $d$. You can see that the problem has a solution if the reduced problem $n'=\frac{n}{d}$ and $k'=\frac{k}{d}$ has a solution. Writing this down is a bit more involved, so I'll explain with one example and you'll get the gist of it from that.

Consider the case where $n=8$ and $k=6$. Clearly $d=2$ is a common divisor and the problem with $n'=4$ and $k'=3$ is solvable as $k'$ is odd (by pressing all buttons). This carries over to a solution for the larger problem. Say you number the lights from 1 to 8. Pressing the buttons at positions $1,3,5,7$ solves the problem with $n=8$ and $k=6$ (the clue here is that we grouped the lightbulbs by $d=2$).

I can show that solutions for a reduced problem yield solutions for the non-reduced problem, however, it's not yet clear to me that each solution of a non-reduced problem stems from a solution of a reduced problem (could be false, I simply don't know).

My goal here is to solve both questions by showing that in case of a common divisor, the problem can be reduced. I think when $\text{gcd}(n,k)=1$, either the problem is solvable and the most efficient solution is obtained by pressing all buttons (haven't proved this yet, but I think this is doable) or $k$ is even and the problem is not solvable. This approach depends entirely on being able to show this reduction idea, but I'm missing something to actually prove that.

Any hints/tips/insights into this reduction idea are welcome.

EDIT: I have an idea whilst on the train. Basically the state space is an n-dimensional vector space over $\mathbb{F}_2$. Each press off a button corresponds to adding a vector consisting of the k sequential ones and the rest are zeroes(and cyclically sequential). A solution writes the vector with only ones as a linear combination of those vectors. This can be a nice way of modeling the problem.

Answer 1

Indeed, linear algebra over $\mathbb F_2$ is the best way to approach this problem. For each $i\in \{0,\dots,n-1\}$, let $v_i$ be the vector with exactly $k$ ones, where the ones are at indices $i,i+1,\dots,i+k-1$. These indices wrap around modulo $n$.

The vectors $v_0,v_1,\dots,v_{n-1}$ span a certain subspace of $\mathbb F_2^n$. The problem is solvable if and only if the all-ones vector is in that subspace. That is, if we can write the all-ones vector in the form $\sum_{i=0}^{n-1} b_i v_i$, where each $b_i\in \{0,1\}$, then we get a solution by pressing the $i^\text{th}$ button if and only if $b_i=1$.

Furthermore, in the case where $v_0,\dots,v_{n-1}$ are linearly independent, then this list is a basis for $\mathbb F_2^n$, so the representation $\sum_i b_iv_i$ for $b_i\in \{0,1\}$ is unique. This uniqueness implies that any solution without repeated button presses is automatically optimal.

Lemma: As long as $k$ is odd and $\gcd(k,n)=1$, then $v_0,\dots,v_{n-1}$ are linearly independent.

Proof: Equivalently, we can prove that $\text{span}(v_0,\dots,v_{n-1})=\mathbb F_2^n$. Letting $e_i$ be the vector with a single $1$ at spot $i$, it suffices to show $e_i\in \text{span}(v_0,\dots,v_{n-1})$ for each $i\in \{0,\dots,n-1\}$.

First, note that $v_i+v_{i+1}$ is a vector with exactly two ones, at spots $i$ and $i+k$. This implies that $v_i+v_{i+1}+v_{k+i}+v_{k+i+1}$ is also a vector with two ones, at spots $i$ and $i+2k$. Continuing this construction, you can show that there is a vector with two ones at spots $i$ and $i+mk\pmod n$ for any $m\ge 0$. This means we can achieve any vector with ones at any locations $i$ and $j$ with $i\neq j\pmod n$, by finding $m$ for which $j=i+mk\pmod n$; this has a solution because $\gcd(k,n)=1$. Therefore, letting $w_i$ be the vector with ones at spots $i$ and $i+1$, we have shown $w_i$ is in the span for all $i\in \{0,\dots,n-1\}$. Conclude by noting $$e_i=v_i+w_{i+1}+w_{i+3}+\dots+w_{i+k-2}.\tag*{$\square$}$$

Therefore, in the case where $k$ is odd and $\gcd(n,k)=1$, we have proved that pressing all $n$ of the buttons is the unique solution which turns on all the lights, so it is the optimal solution.

Now, suppose that $\gcd(k,n)=d>1$. Let $n'=n/d$ and $k'=k/d$. We want to prove that the optimal solution for $(n,k)$ corresponds exactly to the optimal solution for $(n', k')$. We need to show two things:

1. When $k'$ is odd, then the shortest solution involves pressing exactly $n'$ buttons.

2. When $k'$ is even (so necessarily $n'$ is odd), there is no solution.

To prove this, call a light special if its index is a multiple of $d$. There are $n'$ special lights. Each button toggles a contiguous section of $k'$ special lights. Therefore, every solution of the whole ring of lights determines a solution for the ring of special lights alone. This means that when $k'$ is odd, every solution has involves at least $n'$ button presses, and when $k'$ is even, there is no solution. Since there clearly exists a solution with $n'$ button presses when $k'$ is odd (press all of the "special" buttons, whose indices are multiples of $d$), we have proven points $1$ and $2$.