MathLabs

第4問

任意の正整数 tt に対し、0,1,…,t−10,1,\ldots,t-1 の順列 a0,a1,…,at−1a_0,a_1,\ldots,a_{t-1} であって、すべての 0≤i≤t−10\le i\le t-1 について二項係数 (t+i2ai)\binom{t+i}{2a_i} が奇数であり、かつ 2ai≠t+i2a_i\neq t+i を満たすものがただ一つ存在することを証明せよ。
ステップ 1/6: ビット位置集合によるクンマーの定理
前のステップ次のステップ
(t+i2ai) odd  ⟺  S(2ai)⊆S(t+i)\binom{t+i}{2a_i}\text{ odd}\iff S(2a_i)\subseteq S(t+i)
詳しい解説

非負整数 xx に対し、S(x)S(x) を xx の2進展開における数字 11 の位置の集合とする。クンマーの定理によれば、(nk)\binom{n}{k} が奇数であるのはちょうど、kk と n−kn-k を2進で足したときに繰り上がりが生じない場合、すなわち S(k)⊆S(n)S(k)\subseteq S(n) のときである。2ai<t+i2a_i<t+i であるから、2ai≠t+i2a_i\neq t+i という条件と (t+i2ai)\binom{t+i}{2a_i} が奇数であることを合わせると、S(2ai)S(2a_i) は S(t+i)S(t+i) の真部分集合であることを意味する。