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} を求めよ。
ステップ 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} である。