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 を満たすものがただ一つ存在することを証明せよ。
ステップ 4/6: 奇数の添字は直接決まる
前のステップ次のステップ
t+i odd  ⟹  ai=t+i−12t+i\text{ odd}\implies a_i=\frac{t+i-1}{2}
詳しい解説

t+it+i が奇数なら、t+it+i のビット 00 は 11 であるが、2ai2a_i のビット 00 は常に 00 である。S(t+i)S(t+i) のうちちょうど1ビットが S(2ai)S(2a_i) から欠けている（第3段階）ので、その欠けたビットはビット 00 でなければならず、S(2ai)=S(t+i)∖{0}S(2a_i)=S(t+i)\setminus\{0\}、すなわち 2ai=t+i−12a_i=t+i-1、ai=(t+i−1)/2a_i=(t+i-1)/2 となる。これにより t+it+i が奇数であるすべての ii について aia_i が一意に決まる。