A generalization of the lights-out problem

Question

Look here for the original problem.

Let the set $J$ be the set of pairs of positive integers $(m,n)$ with $m\ge n$.

Suppose $(m,n)\in J$. Then there are $m$ lights, which they are initially off. Every step you choose $n$ lights, and you change their states. Let $f:J\rightarrow\mathbb{N}$ be a function such that if there is a way to make all the lights on in a finite number of steps, then $f(m,n)$ be the minimal number of steps. If we can not do this in an finite number of steps, then $f(m,n)=0$. I am interested in the value of $f(m,n)$ These are my primary conclusions: $$f(m,n)=0$$ if $m$ is odd and $n$ is even. $$f(m,n)=3$$ if $m$ and $n$ are the same parity, $m\ne2n$ and $m>n\ge\frac m3$. $$f(m,n)=1$$ if $m=n$ (obvious).

Can anyone help me to solve this puzzle?

Answer 1

Let $q$ be the integer result of dividing $m$ by $n$, and $r$ the remainder of this division. So $m=qn+r$ with $0\le r < n$, and $q$ is the whole number $q=\lfloor\frac{m}{n}\rfloor$.

If you just flip $n$ lights on at a time, after $q$ moves you would have just $r$ lights left. There are a few different cases to consider.

$r=0$:

There are no lights left, so it takes just $q$ moves.

$r+n$ is even, and $q\ge2$.

Flip $q-1$ sets of $n$ lights on, so you have $n+r$ lights left. For the next move flip half of those lights on (i.e. $\frac{n+r}{2}$ on) and the rest of the move switch other lights off (i.e. $n-\frac{n+r}{2}$ lights off). This leaves you with exactly $n$ lights off that you switch on in the next move. This takes $q+1$ moves.
Note that we need $q\ge2$ because there must be lights available to switch off in the second-to-last move.

$r$ is even

This is similar to the previous case but using $r$ instead of $r+n$.
Flip $q$ sets of $n$ lights, so you have $r$ lights left. For the next move flip half of those lights on (i.e. $\frac{r}{2}$ on) and the rest of the move switch other lights off (i.e. $n-\frac{r}{2}$ lights off). This leaves you with exactly $n$ lights off that you switch on in the next move. This takes $q+2$ moves.

$r$ odd, $n$ even (i.e. $m$ odd, $n$ even )

This is impossible. If you always flip an even number of lights, then the total number of lights on will always remain even. You can flip all but one of the lights (just ignore one light, acting as if $m$ is one smaller).

$r$ odd, $n$ odd, $q=1$. This is the trickiest case.

As $m=n+r$ is even we must make an even number of total flips. We flip an odd number of lights in each move, so we need an even number of moves.
Flipping $n$ lights is equivalent to flipping all $m$ of them, and then flipping $m-n=r$ of them back again. As we need an even number of moves and flipping all of them an even number of times does nothing, this case is equivalent to turning on $m$ lights using moves of $r$ lights each time. This game will therefore fall under one of the previous cases that have already been solved.
For example, $m=8, n=5$. We have $q=1$ and $r=3$. This is equivalent to the $m=8$, $n'=r=3$ case. In this new problem we have $m=2*n'+2$, so $q'=2$, $r'=2$. Since $r'$ is even we can solve it in $q'+2=4$ moves.
Note that $q'$ is always at least $2$.

Here is a pictorial view of the various cases:

Answer 2

Very fun puzzle.

I'll start with the obvious cases:

• If m is odd, n is even:

  f(m,n)=-1 (or 0 if you didn't accept my edit); It is not possible as even numbers can never add up to an odd number.

• If m=n:

  f(m,n) = 1; I don't feel the need to explain this lol :)

• If n is a factor of m:

  f(m,n)=m/n; Again, obvious lol

Now the harder cases. Let me define some terms:

• a=m%n (aka the amount of lights left after just turning sets of n on until u can't)
• b: an arbritary number >a. You will eventually reach the point where you have a string of on lights and then a off lights. You switch the state of n lights as usual. When this happens, b is the number of lights that were on that you turn off.

The strategy is to manipulate the lights such that there are n lights off. Mathematically, this means that n=a+b-(n-b).

Simplifying this equation gives you n=a/2 +b. Remember that a, b, & n are all integers. So long as a is even, this equation can always work out,except in cases already highlighted above. This poses a problem if a is odd, and in that case you cannot create n off lights in one step. What you can do is make the number of off lights even, making a even for the next round.

This means that if m%n is odd, f(m,n)= floor(m/n) + 3; The floor(m/n) is setting n lights to on as far as possible. Then 1 more step to make an even number of off lights, 1 more step to make n off lights, and 1 more step to turn the last n on.

And finally:

If m%n is even, f(m,n)= floor(m/n) + 2; The floor(m/n) is setting n lights to on as far as possible. Then 1 more step to make n off lights, and 1 more step to turn the last n on.

This was a good puzzle, thanks.