Problem 4

Prove that for every positive integer

t

there is a unique permutation

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

0,1,\ldots,t-1

such that, for every

0\le i\le t-1

, the binomial coefficient

\binom{t+i}{2a_i}

is odd and

2a_i\neq t+i

Step 3 of 6: Pigeonhole forces a deficit of exactly one bit

Previous step Next step

|S(t+i)|-|S(2a_i)|=1\quad\text{for every }i=0,\ldots,t-1

Detailed analysis

Since $a_0,\ldots,a_{t-1}$ is a permutation of $0,\ldots,t-1$ , the multiset $\{S(2a_i)\}_{i=0}^{t-1}$ equals $\{S(2i)\}_{i=0}^{t-1}$ , so $\sum_i|S(2a_i)|=\sum_i|S(2i)|$ . Combining with the previous identity gives $\sum_i\big(|S(t+i)|-|S(2a_i)|\big)=t$ . Each of the $t$ terms is at least $1$ by Step 1, so every term equals exactly $1$ : $|S(t+i)|-|S(2a_i)|=1$ for every $i$ .