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