设 $n$ 和 $k$ 是正整数，$k\geqslant n$，且 $k-n$ 是一个偶数．$2n$ 盏灯依次编号为 $1,2,\ldots,2n$，每一盏灯可以“开”和“关”．开始时，所有的灯都是“关”的．对这些灯可进行操作，每一次操作只改变其中的一盏灯的开关状态（即“开”变成“关”，“关”变成“开”），我们考虑长度为 $k$ 的操作序列，序列中的第 $i$ 项就是第 $i$ 次操作时被改变开关状态的那盏灯的编号．
设 $N$ 是 $k$ 次操作后使得灯 $1,\ldots,n$ 是“开”的，灯 $n+1,\ldots,2n$ 是“关”的状态的所有不同的操作序列的个数．
设 $M$ 是 $k$ 次操作后使得灯 $1,\ldots,n$ 是“开”的，灯 $n+1,\ldots,2n$ 是“关”的，但是灯 $n+1,\ldots,2n$ 始终没有被开过的所有不同的操作序列的个数．
求比值 $\dfrac{N}{M}$．（法国）
设 $N$ 是 $k$ 次操作后使得灯 $1,\ldots,n$ 是“开”的，灯 $n+1,\ldots,2n$ 是“关”的状态的所有不同的操作序列的个数．
设 $M$ 是 $k$ 次操作后使得灯 $1,\ldots,n$ 是“开”的，灯 $n+1,\ldots,2n$ 是“关”的，但是灯 $n+1,\ldots,2n$ 始终没有被开过的所有不同的操作序列的个数．
求比值 $\dfrac{N}{M}$．（法国）
【难度】
【出处】
2008年第49届IMO试题
【标注】
【答案】
略
【解析】
所求的比值为 $2^{k-n}$．
引理：设 $t$ 是正整数，如果一个 $t$ 元 $0,1$ 数组 $(a_1,a_2,\cdots,a_t)(a_1,a_2,\cdots,a_t\in\{0,1\})$ 其中共有奇数个 $0$，那么称其为"好的"．则好数组共有 $2^{t-1}$ 个．
事实上，对于相同的 $a_1,a_2,\cdots,a_t$ 在 $a_t$ 取 $0,1$ 时得到的两个数组中的奇偶性不同，则恰好有一个为"好的"，于是我们可以将总共 $2^t$ 个不同的可能数组两两配对，每对数组仅有 $a_t$ 不同，则每对恰好有一个好数组，故好数组占总体的一半，即有 $2^{t-1}$ 个．引理得证．
称 $k$ 次操作后灯 $1,\cdots,n$ 是"开"的，灯 $n+1,\cdots,2n$ 是"关"的状态的操作序列的全体记为 $A$ 类型，$k$ 次操作后灯 $1,\cdots,n$ 是"开"的，灯 $n+1,\cdots,2n$ 是"关"的，但是灯 $n+1,\cdots,2n$ 始终没有被操作过的操作序列的全体记为 $B$ 类型．对于任意一个 $B$ 类型 $b$，将有如下性质的 $A$ 类列 $a$ 全部与它对应：" $a$ 的各元素在模 $n$ 的意义下对应相同"（例如，$n=2,k=4$ 时，$b=(2,2,2,1)$ 可对应如 $a=(4,4,2,1),a=(2,2,2,1),a=(2,4,4,1)$ 等），那么由于 $b$ 是 $B$ 类列，其中 $1,2,\cdots,n$ 的个数必定完全为奇数，而 $a$ 是 $A$ 类列，又要求 $a$ 中 $1,\cdots,n$ 的个数全为奇数，且 $n+1,\cdots,2n$ 的个数全为偶数．于是对任意的 $i\in\{1,2,\cdots,n\}$，设 $b$ 中有 $b_i$ 个 $i$，则 $a$ 必须且只需满足：对任意的 $i\in\{1,2,\cdots,n\}$，$b$ 中是 $i$ 的 $b_i$ 个元所在位上在 $a$ 中都是 $i$ 或者 $n+i$，且 $i$ 有奇数个（自然 $n+i$ 就有偶数个），那么由引理及乘法原理，$b$ 恰可对应 $\prod_{i=1}^n2^{b_i-1}=2^{k-n}$ 个不同的 $a$，而每个 $A$ 中的元 $a$ 均有 $B$ 中一元（唯一的一个元）$b$（它是把 $a$ 的各位变成它除以 $n$ 的最小正余数）可以对应它，从而必有 $|A|=2^{k-n}|B|$，即 $N=2^{k-n}M$．又易知 $M\ne 0$（因为操作列 $(1,2,\cdots,n,n,\cdots,n)\in B$），所以 $\dfrac{N}{M}=2^{k-n}$．
引理：设 $t$ 是正整数，如果一个 $t$ 元 $0,1$ 数组 $(a_1,a_2,\cdots,a_t)(a_1,a_2,\cdots,a_t\in\{0,1\})$ 其中共有奇数个 $0$，那么称其为"好的"．则好数组共有 $2^{t-1}$ 个．
事实上，对于相同的 $a_1,a_2,\cdots,a_t$ 在 $a_t$ 取 $0,1$ 时得到的两个数组中的奇偶性不同，则恰好有一个为"好的"，于是我们可以将总共 $2^t$ 个不同的可能数组两两配对，每对数组仅有 $a_t$ 不同，则每对恰好有一个好数组，故好数组占总体的一半，即有 $2^{t-1}$ 个．引理得证．
称 $k$ 次操作后灯 $1,\cdots,n$ 是"开"的，灯 $n+1,\cdots,2n$ 是"关"的状态的操作序列的全体记为 $A$ 类型，$k$ 次操作后灯 $1,\cdots,n$ 是"开"的，灯 $n+1,\cdots,2n$ 是"关"的，但是灯 $n+1,\cdots,2n$ 始终没有被操作过的操作序列的全体记为 $B$ 类型．对于任意一个 $B$ 类型 $b$，将有如下性质的 $A$ 类列 $a$ 全部与它对应：" $a$ 的各元素在模 $n$ 的意义下对应相同"（例如，$n=2,k=4$ 时，$b=(2,2,2,1)$ 可对应如 $a=(4,4,2,1),a=(2,2,2,1),a=(2,4,4,1)$ 等），那么由于 $b$ 是 $B$ 类列，其中 $1,2,\cdots,n$ 的个数必定完全为奇数，而 $a$ 是 $A$ 类列，又要求 $a$ 中 $1,\cdots,n$ 的个数全为奇数，且 $n+1,\cdots,2n$ 的个数全为偶数．于是对任意的 $i\in\{1,2,\cdots,n\}$，设 $b$ 中有 $b_i$ 个 $i$，则 $a$ 必须且只需满足：对任意的 $i\in\{1,2,\cdots,n\}$，$b$ 中是 $i$ 的 $b_i$ 个元所在位上在 $a$ 中都是 $i$ 或者 $n+i$，且 $i$ 有奇数个（自然 $n+i$ 就有偶数个），那么由引理及乘法原理，$b$ 恰可对应 $\prod_{i=1}^n2^{b_i-1}=2^{k-n}$ 个不同的 $a$，而每个 $A$ 中的元 $a$ 均有 $B$ 中一元（唯一的一个元）$b$（它是把 $a$ 的各位变成它除以 $n$ 的最小正余数）可以对应它，从而必有 $|A|=2^{k-n}|B|$，即 $N=2^{k-n}M$．又易知 $M\ne 0$（因为操作列 $(1,2,\cdots,n,n,\cdots,n)\in B$），所以 $\dfrac{N}{M}=2^{k-n}$．
答案
解析
备注
