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 を満たすものがただ一つ存在することを証明せよ。
ステップ 2/6: ビット数の恒等式
前のステップ次のステップ
∑i=0t−1∣S(t+i)∣=t+∑i=0t−1∣S(2i)∣\sum_{i=0}^{t-1}|S(t+i)|=t+\sum_{i=0}^{t-1}|S(2i)|
詳しい解説

S(2i)={1+x:x∈S(i)}S(2i)=\{1+x:x\in S(i)\} かつ S(2i+1)={0}∪{1+x:x∈S(i)}S(2i+1)=\{0\}\cup\{1+x:x\in S(i)\}（2進数字を1つ追加する）であるから、tt に関する短い帰納法により ∑i=0t−1∣S(t+i)∣=t+∑i=0t−1∣S(2i)∣\sum_{i=0}^{t-1}|S(t+i)|=t+\sum_{i=0}^{t-1}|S(2i)| が成り立つ。各段階は tt 個の連続整数にわたる和を、より小さい tt 個の整数にわたる和と、各組 (2i,2i+1)(2i,2i+1) ごとの追加のビット1個に分解する。