MathLabs

第5题

设 nn 和 kk 是正整数，满足 k≥nk \ge n 且 k−nk - n 为偶数。给定 2n2n 盏编号为 1,2,…,2n1, 2, \ldots, 2n 的灯，每盏灯都可以亮或灭。初始时所有灯都熄灭。考虑如下操作序列：每一步切换一盏灯（由亮变灭或由灭变亮）。令 NN 为由 kk 步组成、最终使编号 11 至 nn 的灯全亮且编号 n+1n+1 至 2n2n 的灯全灭的序列数。令 MM 为由 kk 步组成、最终使编号 11 至 nn 的灯全亮且编号 n+1n+1 至 2n2n 的灯全灭、但在整个过程中编号 n+1n+1 至 2n2n 的灯从未被打开的序列数。求 NM\dfrac{N}{M}。
第 1/3 步：用切换次数的奇偶性刻画 N 序列和 M 序列
上一步下一步
通俗地说

从所有灯都熄灭开始，一盏灯最终亮起当且仅当它被切换了奇数次，最终熄灭当且仅当它被切换了偶数次。

A={1,…,n}, B={n+1,…,2n};N:odd on A, even on B;M:odd on A, 0 on BA = \{1,\ldots,n\},\ B = \{n+1,\ldots,2n\}; \quad \mathcal{N}: \text{odd on } A,\ \text{even on } B; \quad \mathcal{M}: \text{odd on } A,\ 0 \text{ on } B
详细分析

将一个 kk 步序列写成 (a1,…,ak)∈(A∪B)k(a_1,\ldots,a_k) \in (A \cup B)^k，其中 A={1,…,n}A=\{1,\ldots,n\} 且 B={n+1,…,2n}B=\{n+1,\ldots,2n\}。集合 N\mathcal{N}（大小为 NN）由每个 i∈Ai \in A 出现奇数次、每个 n+i∈Bn+i \in B 出现偶数次的序列组成；子集 M\mathcal{M}（大小为 MM）由每个 i∈Ai \in A 出现奇数次且 BB 中没有元素出现的序列组成（因为 k≥nk \ge n 且 k−nk - n 为偶数，所以 M>0M > 0）。