2008 IMO Shortlist C4

Let $n$ and $k$ be fixed positive integers of the same parity, $k \geq n$. We are given $2 n$ lamps numbered 1 through $2 n$; each of them can be on or off. At the beginning all lamps are off. We consider sequences of $k$ steps. At each step one of the lamps is switched (from off to on or from on to off). Let $N$ be the number of $k$-step sequences ending in the state: lamps $1, \ldots, n$ on, lamps $n+1, \ldots, 2 n$ off. Let $M$ be the number of $k$-step sequences leading to the same state and not touching lamps $n+1, \ldots, 2 n$ at all. Find the ratio $N / M$.

令 $n$ 和 $k$ 为相同奇偶校验的固定正整数，$k \geq n$。我们得到了 $2 n$ 灯，编号为 1 到 $2 n$；它们每个都可以打开或关闭。开始时所有灯都关闭。我们考虑 $k$ 个步骤的序列。每一步都会切换一个灯(从关闭到打开或从打开到关闭)。令 $N$ 为以以下状态结束的 $k$ 步序列的数量：灯 $1, \ldots, n$ 打开，灯 $n+1, \ldots, 2 n$ 关闭。令 $M$ 为导致相同状态并且根本不接触灯 $n+1, \ldots, 2 n$ 的 $k$ 步序列的数量。求比率 $N / M$。