Problem: Let $n$ and $k$ be positive integers with $k \geq n$ and $k - n$ an even number.
There are $2n$ lamps labelled $1$, $2$, \dots, $2n$ each of which can be either on or off.
Initially all the lamps are off.
We consider sequences of steps: at each step one of the lamps is switched
(from on to off or from off to on).
Let $N$ be the number 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 $M$ be number 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.
Determine $\frac{N}{M}$.

Solution: The answer is $2^{k-n}$.

Consider the following map $\Psi$ from $N$-sequences to $M$-sequences:
\begin{itemize}
  \ii change every instance of $n+1$ to $1$;
  \ii change every instance of $n+2$ to $2$;
  \ii[$\vdots$]
  \ii change every instance of $2n$ to $n$.
\end{itemize}
(For example, suppose $k=9$, $n=3$;
then $144225253 \mapsto 111222223$.)

Clearly this is map is well-defined and surjective.
So all that remains is:
\begin{claim*}
  Every $M$-sequence has exactly $2^{k-n}$ pre-images under $\Psi$.
\end{claim*}
\begin{proof}
  Indeed, suppose that there are $c_1$ instances of lamp $1$.
  Then we want to pick an odd subset of the $1$'s to change to $n+1$'s,
  so $2^{c_1 - 1}$ ways to do this.
  And so on.
  Hence the number of pre-images is
  \[ \prod_i 2^{c_i - 1} = 2^{k-n}. \qedhere \]
\end{proof}