APMO

We constantly make use of Kummer's theorem which, in particular, implies that $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 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)$, $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 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(2i)|.$$ The proof is just realizing that $S(2i)=\{1+x,x\in S(i)\}$ and $S(2i+1)=\{0\}\cup \{1+x,x\in S(i)\}$, because $2i$ in binary is $i$ followed by a zero and $2i+1$ in binary is $i$ followed by a one. Therefore $$\begin{array}{rl}\sum _{i=0}^{t-1}|S(t+i)|& =\sum _{i=0}^{2t-1}|S(i)|-\sum _{i=0}^{t-1}|S(i)|=\sum _{i=0}^{t-1}|S(2i)|+\sum _{i=0}^{t-1}|S(2i+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(2i)|.\end{array}$$ The lemma has an immediate corollary: since $t+i>2a_i$ and $\left(\genfrac{}{}{0ex}{}{t+i}{2a_i}\right)$ is odd for all $i,0\le i\le t-1$, $S\left(2a_i\right)\subset S(t+i)$ with $\left|S\left(2a_i\right)\right|\le |S(t+i)|-1$. Since the sum of $\left|S\left(2a_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(2a_i\right)\right|=|S(t+i)|-1$, which in conjunction with $S\left(2a_i\right)\subset S(t+i)$ means that $t+i-2a_i=2^{k_i}$ for every $i,0\le i\le t-1$, $k_i\in S(t+i)$ (more precisely, $\left\{k_i\right\}=S(t+i)\backslash S\left(2a_i\right)$.) In particular, for $t+i$ odd, this means that $t+i-2a_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 $\left(\genfrac{}{}{0ex}{}{t+i}{2a_i}\right)\equiv \left(\frac{t+i}{a_i}\right)(\mathrm{mod}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\to 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,\dots ,\lfloor t/2\rfloor -1\}$ (the set of small numbers) and $B_t=\{\lceil t/2\rceil ,\dots ,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\le 2^a<t⟺a=\lceil {\log }_2(t/2)\rceil$. Let $2^a$ be this power of two. Then, since $2^a\ge t/2$, no number in $A_t$ has a one in position $a$ in binary. Since for every number $x,2^a\le 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\le x<t$, and $y\in A_t,0\le y<t-2^a$. Now we need to pair the numbers from $A^{\prime }=\left\{t-2^a,t-2^a+1,\dots ,\lfloor t/2\rfloor -1\right\}\subset A$ with the numbers from $B^{\prime }=\left\{\lceil t/2\rceil ,\lceil t/2\rceil +1,\dots ,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,\dots ,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\le x\le \lfloor \frac{2^{a+1}-t}{2}\rfloor -1=2^a-\lceil \frac{t}{2}\rceil -1⟺\lceil \frac{t}{2}\rceil \le 2^a-1-x\le 2^a-1$$ and $$\lceil \frac{2^{a+1}-t}{2}\rceil =2^a-\lfloor \frac{t}{2}\rfloor \le y\le 2^{a+1}-t-1⟺t-2^a\le 2^a-1-y\le \lfloor \frac{t}{2}\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,\dots ,10\},B_{23}=\{12,13,14,\dots ,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)\to \left(\begin{array}{llll}5& 6& 7& 8\\ 1& 2& 3& 0\end{array}\right).$$