# 熄燈問題的一般化

here中查找原始問題。

Very fun puzzle.

• If m is odd, n is even:

• If m=n:

• If n is a factor of m:

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.

And finally:

This was a good puzzle, thanks.

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$$:

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

$$r$$ is even

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

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

Here is a pictorial view of the various cases: