International Mathematical Olympiad

Lemma For any positive integer $t$, call a $t$-element array $(a_1,a_2,\dots ,a_t)$ which consists of $0,1$ ($a_1,a_2,\dots ,a_t\in \{0,1\}$) "good" if there are odd '0's in it. Prove that there are $2^{t-1}$ "good" arrays.

Proof: In fact, for the same $a_1,a_2,\dots ,a_t$, when $a_t$ is 0 or 1, the parity of 0s in these two arrays is different, so only one of the arrays is "good". There are $2^t$ arrays in all, we can match one array to the other, there are only $a_t$ of them are different. Only one of these two arrays is "good". So of all the possible arrays, only half of them are "good". The lemma is proved.

Let $A$ be the set of such sequences consisting of $k$ steps and resulting in the state where lamps $1$ through $n$ are all on, and lamps $n+1$ through $2n$ are all off. Let $B$ be the set of such sequences consisting of $k$ steps, resulting in the state where lamps $1$ through $n$ are all on, and lamps $n+1$ through $2n$ are all off, but where none of the lamps $n+1$ through $2n$ is ever switched on.

For any $b$ in $B$, match all $a$ in $A$ to $b$ if "a's elements are the same as $b$'s (mod $n$)" (For example, take $n=2,k=4$, if $b=(2,2,2,1)$, then it could correspond to $a=(4,4,2,1)$, $a=(2,2,2,1)$, $a=(2,4,4,1)$ etc). Since $b$ in $B$, the number of $1,2,\dots ,n$ must be odd; $a$ in $A$, the number of $1,2,\dots ,n$ of $b$ must be odd, and the number of $n+1,\dots ,2n$ must be even.

For any $i\in \{1,2,\dots ,n\}$, if number of 'i's in $b$ is $b_i$, then $a$ only need to satisfy: for the positions taken by $i$ in $b$ the corresponding positions taken by $i$ or $n+i$ in $a$, and the number of 'i's is odd (thus the number of $n+i$ is even). By lemma and the product principle, there are ${\prod }_{i=1}^n{2}^{b_i-1}=2^{k-n}$ 'a's corresponding to $b$, but only one of $b$ (letting every position of $a$ be the remainder when divided by $n$) in $B$ corresponds to each $a$ in $A$.

Therefore $|A|=2^{k-n}|B|$, i.e. $N=2^{k-n}M$.

Obviously $M\ne 0$ (because the sequence $(1,2,\dots ,n,n,\cdots ,n)\in B$), so $$\frac{N}{M}=2^{k-n}.$$