第4問

任意の正整数

t

に対し、

0,1,\ldots,t-1

の順列

a_0,a_1,\ldots,a_{t-1}

であって、すべての

0\le i\le t-1

について二項係数

\binom{t+i}{2a_i}

が奇数であり、かつ

2a_i\neq t+i

を満たすものがただ一つ存在することを証明せよ。

ステップ 5/6: 偶数の添字はビットの対合わせに帰着する

前のステップ次のステップ

t+i=2m\text{ even}\implies S(a_i)\subsetneq S(m),\ |S(a_i)|=|S(m)|-1

詳しい解説

$t+i=2m$ が偶数なら、第3段階の欠けたビットはある位置 $k\ge1$ であり、 $2a_i=2m-2^k$ 、 $a_i=m-2^{k-1}$ となる。つまり $S(a_i)=S(m)\setminus\{k-1\}$ であり、ちょうど1ビット少ない真部分集合である。第4段階の奇数添字の式が、まさに『大きい』値 $m\in\{\lceil t/2\rceil,\ldots,t-1\}$ を $a_i$ として実現することが確認できるので、残りの偶数添字の $a_i$ の値は『小さい』数 $\{0,\ldots,\lceil t/2\rceil-1\}$ からこれらの大きい数 $m$ への全単射でなければならず、 $S(a_i)\subsetneq S(m)$ かつ $|S(a_i)|=|S(m)|-1$ を満たす。