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 5 of 6: The even indices reduce to a bit-pairing

Previous step Next step

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

Detailed analysis

If $t+i=2m$ is even, the missing bit from Step 3 is some position $k\ge1$ , so $2a_i=2m-2^k$ and $a_i=m-2^{k-1}$ ; equivalently $S(a_i)=S(m)\setminus\{k-1\}$ , a proper subset with exactly one fewer bit. One checks that the odd-index formula of Step 4 realizes exactly the 'big' values $m\in\{\lceil t/2\rceil,\ldots,t-1\}$ as $a_i$ , so the remaining, even-index values of $a_i$ must be a bijection from the 'small' numbers $\{0,\ldots,\lceil t/2\rceil-1\}$ onto these same big numbers $m$ , satisfying $S(a_i)\subsetneq S(m)$ with $|S(a_i)|=|S(m)|-1$ .