This poses a problem if a is odd, and in that case you cannot create n off lights in one step. So long as a is even, this equation can always work out,except in cases already highlighted above. Remember that a, b, & n are all integers. Simplifying this equation gives you n=a/2 +b. Mathematically, this means that n=a+b-(n-b). The strategy is to manipulate the lights such that there are n lights off. When this happens, b is the number of lights that were on that you turn off. You switch the state of n lights as usual. You will eventually reach the point where you have a string of on lights and then a off lights. a=m%n (aka the amount of lights left after just turning sets of n on until u can't).Here is a pictorial view of the various cases:į(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.į(m,n) = 1 I don't feel the need to explain this lol :) Since $r'$ is even we can solve it in $q'+2=4$ moves. This is equivalent to the $m=8$, $n'=r=3$ case. This game will therefore fall under one of the previous cases that have already been solved.įor example, $m=8, n=5$. 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. We flip an odd number of lights in each move, so we need an even number of moves.įlipping $n$ lights is equivalent to flipping all $m$ of them, and then flipping $m-n=r$ of them back again. This is the trickiest case.Īs $m=n+r$ is even we must make an even number of total flips. You can flip all but one of the lights (just ignore one light, acting as if $m$ is one smaller).
If you always flip an even number of lights, then the total number of lights on will always remain even. This leaves you with exactly $n$ lights off that you switch on in the next move. So $m=qn+r$ with $0\le r < n$, and $q$ is the whole number $q=\lfloor\frac$ lights off). Let $q$ be the integer result of dividing $m$ by $n$, and $r$ the remainder of this division.
0 kommentar(er)
