49th International Mathematical Olympiad Spain

It is well-known that all these numbers are odd. So the assertion that their remainders $(\mathrm{mod}{2}^n)$ make up a permutation of $\{1,3,\dots ,2^n-1\}$ is equivalent just to saying that these remainders are all distinct. We begin by showing that $$\begin{array}{c}\left(\genfrac{}{}{0ex}{}{2^n-1}{2k}\right)+\left(\genfrac{}{}{0ex}{}{2^n-1}{2k+1}\right)\equiv 0\left(\mathrm{mod}{2}^n\right)\text{ and }\left(\genfrac{}{}{0ex}{}{2^n-1}{2k}\right)\equiv (-1{)}^k(\genfrac{}{}{0ex}{}{2^{n-1}-1}{k})\left(\mathrm{mod}{2}^n\right).\end{array}\text{\hspace{1em}(1)}$$ The first relation is immediate, as the sum on the left is equal to $\left(\genfrac{}{}{0ex}{}{2^n}{2k+1}\right)=\frac{2^n}{2k+1}\left(\genfrac{}{}{0ex}{}{2^n-1}{2k}\right)$, hence is divisible by $2^n$. The second relation: $$\left(\genfrac{}{}{0ex}{}{2^n-1}{2k}\right)=\prod _{j=1}^{2k}\frac{2^n-j}{j}=\prod _{i=1}^k\frac{2^n-(2i-1)}{2i-1}\cdot \prod _{i=1}^k\frac{2^{n-1}-i}{i}\equiv (-1{)}^k(\genfrac{}{}{0ex}{}{2^{n-1}-1}{k})\left(\mathrm{mod}{2}^n\right).$$ This prepares ground for a proof of the required result by induction on $n$. The base case $n=1$ is obvious. Assume the assertion is true for $n-1$ and pass to $n$, denoting $a_k=\left(\genfrac{}{}{0ex}{}{2^{n-1}-1}{k}\right)$, $b_m=\left(\genfrac{}{}{0ex}{}{2^n-1}{m}\right)$. The induction hypothesis is that all the numbers $a_k\left(0\le k<2^{n-2}\right)$ are distinct $\left(\mathrm{mod}{2}^{n-1}\right)$; the claim is that all the numbers $b_m\left(0\le m<2^{n-1}\right)$ are distinct $\left(\mathrm{mod}{2}^n\right)$. The congruence relations (1) are restated as $$\begin{array}{c}{b}_{2k}\equiv (-1{)}^k{a}_k\equiv -b_{2k+1}\left(\mathrm{mod}{2}^n\right)\end{array}\text{\hspace{1em}(2)}$$ Shifting the exponent in the first relation of (1) from $n$ to $n-1$ we also have the congruence $a_{2i+1}\equiv -a_{2i}\left(\mathrm{mod}{2}^{n-1}\right)$. We hence conclude: If, for some $j,k<2^{n-2},a_k\equiv -a_j\left(\mathrm{mod}{2}^{n-1}\right)$, then $\{j,k\}=\{2i,2i+1\}$ for some $i$. This is so because in the sequence $\left(a_k:k<2^{n-2}\right)$ each term $a_j$ is complemented to $0\left(\mathrm{mod}{2}^{n-1}\right)$ by only one other term $a_k$, according to the induction hypothesis. From (2) we see that $b_{4i}\equiv a_{2i}$ and $b_{4i+3}\equiv a_{2i+1}\left(\mathrm{mod}{2}^n\right)$. Let $$M=\{m:0\le m<2^{n-1},m\equiv 0\text{ or }3(\mathrm{mod}4)\},L=\{l:0\le l<2^{n-1},l\equiv 1\text{ or }2(\mathrm{mod}4)\}.$$ The last two congruences take on the unified form $$\begin{array}{c}{b}_m\equiv a_{\lfloor m/2\rfloor }\left(\mathrm{mod}{2}^n\right)\text{ for all }m\in M\end{array}\text{\hspace{1em}(4)}$$ Thus all the numbers $b_m$ for $m\in M$ are distinct $\left(\mathrm{mod}{2}^n\right)$ because so are the numbers $a_k$ (they are distinct $\left(\mathrm{mod}{2}^{n-1}\right)$, hence also $\left(\mathrm{mod}{2}^n\right))$. Every $l\in L$ is paired with a unique $m\in M$ into a pair of the form $\{2k,2k+1\}$. So (2) implies that also all the $b_l$ for $l\in L$ are distinct $\left(\mathrm{mod}{2}^n\right)$. It remains to eliminate the possibility that $b_m\equiv b_l\left(\mathrm{mod}{2}^n\right)$ for some $m\in M,l\in L$. Suppose that such a situation occurs. Let $m^{\prime }\in M$ be such that $\{m^{\prime },l\}$ is a pair of the form $\{2k,2k+1\}$, so that (see (2)) $b_{m^{\prime }}\equiv -b_l\left(\mathrm{mod}{2}^n\right)$. Hence $b_{m^{\prime }}\equiv -b_m\left(\mathrm{mod}{2}^n\right)$. Since both $m^{\prime }$ and $m$ are in $M$, we have by (4) $b_{m^{\prime }}\equiv a_j,b_m\equiv a_k\left(\mathrm{mod}{2}^n\right)$ for $j=\lfloor m^{\prime }/2\rfloor ,k=\lfloor m/2\rfloor$. Then $a_j\equiv -a_k\left(\mathrm{mod}{2}^n\right)$. Thus, according to $(3),j=2i,k=2i+1$ for some $i$ (or vice versa). The equality $a_{2i+1}\equiv -a_{2i}\left(\mathrm{mod}{2}^n\right)$ now means that $\left(\genfrac{}{}{0ex}{}{2^{n-1}-1}{2i}\right)+\left(\genfrac{}{}{0ex}{}{2^{n-1}-1}{2i+1}\right)\equiv 0\left(\mathrm{mod}{2}^n\right)$. However, the sum on the left is equal to $\left(\genfrac{}{}{0ex}{}{2^{n-1}}{2i+1}\right)$. A number of this form cannot be divisible by $2^n$. This is a contradiction which concludes the induction step and proves the result.

---

Alternative solution.

We again proceed by induction, writing for brevity $N=2^{n-1}$ and keeping notation $a_k=\left(\genfrac{}{}{0ex}{}{N-1}{k}\right),b_m=\left(\genfrac{}{}{0ex}{}{2N-1}{m}\right)$. Assume that the result holds for the sequence $\left(a_0,a_1,a_2,\dots ,a_{N/2-1}\right)$. In view of the symmetry $a_{N-1-k}=a_k$ this sequence is a permutation of $\left(a_0,a_2,a_4,\dots ,a_{N-2}\right)$. So the induction hypothesis says that this latter sequence, taken $(\mathrm{mod}N)$, is a permutation of $(1,3,5,\dots ,N-1)$. Similarly, the induction claim is that $\left(b_0,b_2,b_4,\dots ,b_{2N-2}\right)$, taken $(\mathrm{mod}2N)$, is a permutation of $(1,3,5,\dots ,2N-1)$. In place of the congruence relations (2) we now use the following ones, $$\begin{array}{c}{b}_{4i}\equiv a_{2i}(\mathrm{mod}N)\text{ and }{b}_{4i+2}\equiv b_{4i}+N(\mathrm{mod}2N)\end{array}\text{\hspace{1em}(5)}$$ Given this, the conclusion is immediate: the first formula of (5) together with the induction hypothesis tells us that $\left(b_0,b_4,b_8,\dots ,b_{2N-4}\right)(\mathrm{mod}N)$ is a permutation of $(1,3,5,\dots ,N-1)$. Then the second formula of (5) shows that $\left(b_2,b_6,b_{10},\dots ,b_{2N-2}\right)(\mathrm{mod}N)$ is exactly the same permutation; moreover, this formula distinguishes $(\mathrm{mod}2N)$ each $b_{4i}$ from $b_{4i+2}$. Consequently, these two sequences combined represent $(\mathrm{mod}2N)$ a permutation of the sequence $(1,3,5,\dots ,N-1,N+1,N+3,N+5,\dots ,N+N-1)$, and this is precisely the induction claim. Now we prove formulas (5); we begin with the second one. Since $b_{m+1}=b_m\cdot \frac{2N-m-1}{m+1}$, $$b_{4i+2}=b_{4i}\cdot \frac{2N-4i-1}{4i+1}\cdot \frac{2N-4i-2}{4i+2}=b_{4i}\cdot \frac{2N-4i-1}{4i+1}\cdot \frac{N-2i-1}{2i+1}.$$ The desired congruence $b_{4i+2}\equiv b_{4i}+N$ may be multiplied by the odd number ( $4i+1$ ) ( $2i+1$ ), giving rise to a chain of successively equivalent congruences: $$\begin{array}{rlrl}{b}_{4i}(2N-4i-1)(N-2i-1)& \equiv \left(b_{4i}+N\right)(4i+1)(2i+1)& & (\mathrm{mod}2N),\\ b_{4i}(2i+1-N)& \equiv \left(b_{4i}+N\right)(2i+1)& & (\mathrm{mod}2N),\\ \left(b_{4i}+2i+1\right)N& \equiv 0& & (\mathrm{mod}2N);\end{array}$$ and the last one is satisfied, as $b_{4i}$ is odd. This settles the second relation in (5). The first one is proved by induction on $i$. It holds for $i=0$. Assume $b_{4i}\equiv a_{2i}(\mathrm{mod}2N)$ and consider $i+1$ : $$b_{4i+4}=b_{4i+2}\cdot \frac{2N-4i-3}{4i+3}\cdot \frac{2N-4i-4}{4i+4};a_{2i+2}=a_{2i}\cdot \frac{N-2i-1}{2i+1}\cdot \frac{N-2i-2}{2i+2}.$$ Both expressions have the fraction $\frac{N-2i-2}{2i+2}$ as the last factor. Since $2i+2<N=2^{n-1}$, this fraction reduces to $\ell /m$ with $\ell$ and $m$ odd. In showing that $b_{4i+4}\equiv a_{2i+2}(\mathrm{mod}2N)$, we may ignore this common factor $\ell /m$. Clearing other odd denominators reduces the claim to $$b_{4i+2}(2N-4i-3)(2i+1)\equiv a_{2i}(N-2i-1)(4i+3)(\mathrm{mod}2N)$$ By the inductive assumption (saying that $b_{4i}\equiv a_{2i}(\mathrm{mod}2N)$ ) and by the second relation of (5), this is equivalent to $$\left(b_{4i}+N\right)(2i+1)\equiv b_{4i}(2i+1-N)(\mathrm{mod}2N)$$ a congruence which we have already met in the preceding proof a few lines above. This completes induction (on $i$ ) and the proof of (5), hence also the whole solution.