49-я Международная Математическая OлимпиадаИспания, Мадрид, 2008 год

Пусть $n$ и $k$ такие натуральные числа, что $k\ge n$, а число $n-k$ четное. Имеется $2n$ лампочек, занумерованных числами $1$, $2$, $\ldots $, $2n$, каждая из которых может находиться в одном из двух состояний: вкл. (включена) или выкл. (выключена). Вначале все лампочки были выключены. Рассматриваются упорядоченные последовательности шагов: на каждом шаге ровно одна из лампочек меняет свое состояние на противоположное (с вкл. на выкл. либо с выкл. на вкл.). Обозначим через $N$ количество последовательностей из $k$ шагов, приводящих к ситуации, в которой все лампочки с 1-й по $n$-ю включены, а все лампочки с $\left( n+1 \right)$-й по $\left( 2n \right)$-ю выключены.
Обозначим через $M$ количество последовательностей из к шагов, приводящих к ситуации, в которой также все лампочки с 1-й по $n$-ю включены, все лампочки с $\left( n+1 \right)$-й по $\left( 2n \right)$-ю выключены, но при этом ни одна из лампочек с $\left( n+1 \right)$-й по $\left( 2n \right)$-ю ни разу не меняла своего состояния. Найдите значение отношения $\dfrac{N}{M}$.