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}。
第 2/3 步：定义从 N 序列到 M 序列的折叠映射 f
上一步下一步
通俗地说

将灯 n+in+i 的每次切换折叠到灯 ii 上，会给灯 ii 增加偶数次切换，保持其总次数为奇数，同时消除 BB 中的所有切换。

f(a1,…,ak)=(b1,…,bk),br={ar,ar∈Aar−n,ar∈Bf(a_1,\ldots,a_k) = (b_1,\ldots,b_k), \qquad b_r = \begin{cases} a_r, & a_r \in A \\ a_r - n, & a_r \in B \end{cases}
详细分析

定义 f:N→Mf: \mathcal{N} \to \mathcal{M}：将每个 n+i∈Bn+i \in B 的项替换为 i∈Ai \in A。因为在任意 (a1,…,ak)∈N(a_1,\ldots,a_k) \in \mathcal{N} 中 n+in+i 出现偶数次而 ii 出现奇数次，所以像 f(a1,…,ak)f(a_1,\ldots,a_k) 中每个 i∈Ai \in A 出现奇数加偶数 = 奇数次，且不含 BB 中的项，故 f(N)⊆Mf(\mathcal{N}) \subseteq \mathcal{M}。