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 4 of 6: The odd indices are determined directly

Previous step Next step

t+i\text{ odd}\implies a_i=\frac{t+i-1}{2}

Detailed analysis

If $t+i$ is odd, bit $0$ of $t+i$ is $1$ , while bit $0$ of $2a_i$ is always $0$ . Since exactly one bit of $S(t+i)$ is missing from $S(2a_i)$ (Step 3), that missing bit must be bit $0$ , so $S(2a_i)=S(t+i)\setminus\{0\}$ , that is, $2a_i=t+i-1$ and $a_i=(t+i-1)/2$ . This pins down $a_i$ uniquely for every $i$ with $t+i$ odd.