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}。
第 3/3 步：计算每个 M 序列的原像并得出 N/M = 2^(k-n)
上一步下一步
通俗地说

对每个 y∈My \in \mathcal{M}，若灯 ii 被切换 li≥1l_i \ge 1 次，从这 lil_i 次中任取偶数大小的子集提升为 n+in+i，每个 ii 有 2li−12^{l_i-1} 种选择；对 i=1,…,ni=1,\ldots,n 相乘得到 2k−n2^{k-n}。

∣f−1(y)∣=∏i=1n((li0)+(li2)+⋯ )=∏i=1n2li−1=2∑i=1nli−n=2k−n  ⟹  NM=2k−n|f^{-1}(y)| = \prod_{i=1}^n \left(\binom{l_i}{0}+\binom{l_i}{2}+\cdots\right) = \prod_{i=1}^n 2^{l_i-1} = 2^{\sum_{i=1}^n l_i - n} = 2^{k-n} \implies \frac{N}{M} = 2^{k-n}
详细分析

固定 y∈My \in \mathcal{M}，其中每个 i∈Ai \in A 出现 li≥1l_i \ge 1 次（且 ∑i=1nli=k\sum_{i=1}^n l_i = k）。序列 x∈Nx \in \mathcal{N} 满足 f(x)=yf(x) = y 当且仅当，对每个 i∈Ai \in A，将 yy 中 ii 的 lil_i 次出现中的偶数次替换为 n+in+i 即可得到 xx。大小为 li≥1l_i \ge 1 的集合有 (li0)+(li2)+⋯=2li−1\binom{l_i}{0}+\binom{l_i}{2}+\cdots = 2^{l_i-1} 个偶数大小子集，而各个 i=1,…,ni = 1,\ldots,n 的选择相互独立，因此 ∣f−1(y)∣=∏i=1n2li−1=2∑i=1nli−n=2k−n|f^{-1}(y)| = \prod_{i=1}^n 2^{l_i-1} = 2^{\sum_{i=1}^n l_i - n} = 2^{k-n}。对所有 y∈My \in \mathcal{M} 求和得到 N=2k−nMN = 2^{k-n} M，所以 NM=2k−n\dfrac{N}{M} = 2^{k-n}。