Problem 2308

We constantly make use of Kummer's theorem which, in particular, implies that $\binom{n}{k}$ is odd if and only if $k$ and $n-k$ have ones in different positions in binary. In other words, if $S(x)$ is the set of positions of the digits 1 of $x$ in binary (in which the digit multiplied by $2^{i}$ is in position $i)$, $\binom{n}{k}$ is odd if and only if $S(k) \subseteq S(n)$. Moreover, if we set $k<n, S(k)$ is a proper subset of $S(n)$, that is, $|S(k)|<|S(n)|$.
We start with a lemma that guides us how the permutation should be set.

Lemma 1.
$$\sum_{i=0}^{t-1}|S(t+i)|=t+\sum_{i=0}^{t-1}|S(2 i)| .$$
The proof is just realizing that $S(2 i)=\{1+x, x \in S(i)\}$ and $S(2 i+1)=\{0\} \cup\{1+x, x \in S(i)\}$, because $2 i$ in binary is $i$ followed by a zero and $2 i+1$ in binary is $i$ followed by a one. Therefore
$$\begin{aligned} \sum_{i=0}^{t-1}|S(t+i)| & =\sum_{i=0}^{2 t-1}|S(i)|-\sum_{i=0}^{t-1}|S(i)|=\sum_{i=0}^{t-1}|S(2 i)|+\sum_{i=0}^{t-1}|S(2 i+1)|-\sum_{i=0}^{t-1}|S(i)| \\ & =\sum_{i=0}^{t-1}|S(i)|+\sum_{i=0}^{t-1}(1+|S(i)|)-\sum_{i=0}^{t-1}|S(i)|=t+\sum_{i=0}^{t-1}|S(i)|=t+\sum_{i=0}^{t-1}|S(2 i)| . \end{aligned}$$
The lemma has an immediate corollary: since $t+i>2 a_{i}$ and $\binom{t+i}{2 a_{i}}$ is odd for all $i, 0 \leq i \leq t-1$, $S\left(2 a_{i}\right) \subset S(t+i)$ with $\left|S\left(2 a_{i}\right)\right| \leq|S(t+i)|-1$. Since the sum of $\left|S\left(2 a_{i}\right)\right|$ is $t$ less than the sum of $|S(t+i)|$, and there are $t$ values of $i$, equality must occur, that is, $\left|S\left(2 a_{i}\right)\right|=|S(t+i)|-1$, which in conjunction with $S\left(2 a_{i}\right) \subset S(t+i)$ means that $t+i-2 a_{i}=2^{k_{i}}$ for every $i, 0 \leq i \leq t-1$, $k_{i} \in S(t+i)$ (more precisely, $\left\{k_{i}\right\}=S(t+i) \backslash S\left(2 a_{i}\right)$.)
In particular, for $t+i$ odd, this means that $t+i-2 a_{i}=1$, because the only odd power of 2 is 1. Then $a_{i}=\frac{t+i-1}{2}$ for $t+i$ odd, which takes up all the numbers greater than or equal to $\frac{t-1}{2}$. Now we need to distribute the numbers that are smaller than $\frac{t-1}{2}$ (call these numbers small). If $t+i$ is even then by Lucas' Theorem $\binom{t+i}{2 a_{i}} \equiv\left(\frac{t+i}{a_{i}}\right)(\bmod 2)$, so we pair numbers from $\lceil t / 2\rceil$ to $t-1$ (call these numbers big) with the small numbers.
Say that a set $A$ is paired with another set $B$ whenever $|A|=|B|$ and there exists a bijection $\pi: A \rightarrow B$ such that $S(a) \subset S(\pi(a))$ and $|S(a)|=|S(\pi(a))|-1$; we also say that $a$ and $\pi(a)$ are paired. We prove by induction in $t$ that $A_{t}=\{0,1,2, \ldots,\lfloor t / 2\rfloor-1\}$ (the set of small numbers) and $B_{t}=\{\lceil t / 2\rceil, \ldots, t-2, t-1\}$ (the set of big numbers) can be uniquely paired.
The claim is immediate for $t=1$ and $t=2$. For $t>2$, there is exactly one power of two in $B_{t}$, since $t / 2 \leq 2^{a}<t \Longleftrightarrow a=\left\lceil\log _{2}(t / 2)\right\rceil$. Let $2^{a}$ be this power of two. Then, since $2^{a} \geq t / 2$, no number in $A_{t}$ has a one in position $a$ in binary. Since for every number $x, 2^{a} \leq x<t, a \in S(x)$ and $a \notin S(y)$ for all $y \in A_{t}, x$ can only be paired with $x-2^{a}$, since $S(x)$ needs to be stripped of exactly one position. This takes cares of $x \in B_{t}, 2^{a} \leq x<t$, and $y \in A_{t}, 0 \leq y<t-2^{a}$.
Now we need to pair the numbers from $A^{\prime}=\left\{t-2^{a}, t-2^{a}+1, \ldots,\lfloor t / 2\rfloor-1\right\} \subset A$ with the numbers from $B^{\prime}=\left\{\lceil t / 2\rceil,\lceil t / 2\rceil+1, \ldots, 2^{a}-1\right\} \subset B$. In order to pair these $t-2\left(t-2^{a}\right)= 2^{a+1}-t<t$ numbers, we use the induction hypothesis and a bijection between $A^{\prime} \cup B^{\prime}$ and $B_{2^{a+1}-t} \cup A_{2^{a+1}-t}$. Let $S=S\left(2^{a}-1\right)=\{0,1,2, \ldots, a-1\}$. Then take a pair $x, y, x \in A_{2^{a+1}-t}$ and $y \in B_{2^{a+1}-t}$ and biject it with $2^{a}-1-x \in B^{\prime}$ and $2^{a}-1-y \in A^{\prime}$. In fact,
$$0 \leq x \leq\left\lfloor\frac{2^{a+1}-t}{2}\right\rfloor-1=2^{a}-\left\lceil\frac{t}{2}\right\rceil-1 \Longleftrightarrow\left\lceil\frac{t}{2}\right\rceil \leq 2^{a}-1-x \leq 2^{a}-1$$
and
$$\left\lceil\frac{2^{a+1}-t}{2}\right\rceil=2^{a}-\left\lfloor\frac{t}{2}\right\rfloor \leq y \leq 2^{a+1}-t-1 \Longleftrightarrow t-2^{a} \leq 2^{a}-1-y \leq\left\lfloor\frac{t}{2}\right\rfloor-1 .$$
Moreover, $S\left(2^{a}-1-x\right)=S \backslash S(x)$ and $S\left(2^{a}-1-y\right)=S \backslash S(y)$ are complements with respect to $S$, and $S(x) \subset S(y)$ and $|S(x)|=|S(y)|-1$ implies $S\left(2^{a}-1-y\right) \subset S\left(2^{a}-1-x\right)$ and $\left|S\left(2^{a}-1-y\right)\right|=\left|S\left(2^{a}-1-x\right)\right|-1$. Therefore a pairing between $A^{\prime}$ and $B^{\prime}$ corresponds to a pairing between $A_{2^{a+1}-t}$ and $B_{2^{a+1}-t}$. Since the latter pairing is unique, the former pairing is also unique, and the result follows.
We illustrate the bijection by showing the case $t=23$ :
$$A_{23}=\{0,1,2, \ldots, 10\}, \quad B_{23}=\{12,13,14, \ldots, 22\} .$$
The pairing is
$$\left(\begin{array}{ccccccccccc} 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 \\ 8 & 9 & 10 & 7 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \end{array}\right),$$
in which the bijection is between
$$\left(\begin{array}{cccc} 12 & 13 & 14 & 15 \\ 8 & 9 & 10 & 7 \end{array}\right) \text{ and }\left(\begin{array}{llll} 3 & 2 & 1 & 0 \\ 7 & 6 & 5 & 8 \end{array}\right) \rightarrow\left(\begin{array}{llll} 5 & 6 & 7 & 8 \\ 1 & 2 & 3 & 0 \end{array}\right) .$$