MathLabs

第5問

nn と kk を k≥nk \ge n かつ k−nk - n が偶数を満たす正の整数とする。1,2,…,2n1, 2, \ldots, 2n と番号づけられた 2n2n 個のランプがあり、それぞれ点灯または消灯できる。初めはすべて消灯している。各段階でランプを一つ切り替える（点灯から消灯、または消灯から点灯）操作列を考える。NN を、kk 段階でランプ 11 から nn がすべて点灯し、ランプ n+1n+1 から 2n2n がすべて消灯する状態になる列の数とする。MM を、ランプ 11 から nn がすべて点灯し、ランプ n+1n+1 から 2n2n がすべて消灯する状態に至る kk 段階の列のうち、ランプ 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} である。