2022 China Team Selection Test for IMO

The $n$-tuples we seek are the ones satisfying the following condition: if there are exactly $r$ odd numbers in $a_2,\dots ,a_n$, then $2^r\mid a_1-1$. $(\ast )$

We first verify the necessity of $(\ast )$. For this, we drop the condition $a_n\ge a_{n-1}\ge \cdots \ge a_1$ and assume that $a_1,\dots ,a_r$ are odd and $a_{r+1},\dots ,a_n$ are even. Suppose that we are given the $M$ tuples satisfying the requirement (2). For each $s\in \mathbb{Z}$, denote $B_s=\{i\mid 1\le i\le M,c_{i,n}\equiv s(\mathrm{mod}{a}_n)\}$. Then $$|B_1|+|B_2|+\cdots +|B_{a_n}|=M.$$ Consequently, there exists an index $s$ such that $|B_s|+|B_{s+1}|\ge \frac{M}{a_n/2}$. This means that we can choose at least $\frac{M}{a_n/2}$ tuples such that the differences between their $n$-th coordinates $c_{i,n}$ are all congruent to $0$ or $\pm 1$ modulo $a_n$.

By running the same argument for all the tuples inductively, i.e., to consider the $(n-1)$th coordinates modulo $a_{n-1}$, the $(n-2)$th coordinates modulo $a_{n-2}$, etc., it eventually shows that there are at least $\frac{M}{\frac{a_n}{2}\dots \frac{a_2}{2}}=\frac{a_1-1}{2}$ tuples such that for each two of them, the differences between their $k$th coordinates $c_{i,k}$'s are congruent to $0$ or $\pm 1$ modulo $a_k$, where $2\le k\le n$. However, the given conditions imply that the difference between the first coordinates of these tuples can not be $0$ or $\pm 1$ (mod $a_1$); there are at most $\frac{a_1-1}{2}$ such tuples. This means that all equalities must hold in the argument above. Namely, for each $t$ we have exactly $\frac{M}{\frac{a_n}{2}\dots \frac{a_t}{2}}$ different tuples. In particular, taking $t=r+1$ leads to $$\frac{M}{\frac{a_n}{2}\dots \frac{a_{r+1}}{2}}=\frac{1}{2^r}(a_1-1)a_2\dots a_r\in \mathbb{Z}.$$ It forces that $2^r\mid a_1-1$.

In the following, we construct the needed $M$ tuples under the condition $2^r\mid a_1-1$. For convenience, we first weaken the condition $a_n\ge a_{n-1}\ge \cdots \ge a_1$ to only requiring $a_1=\min \{a_1,\dots ,a_n\}$. Whenever there is any even number in $a_2,\dots ,a_n$, say $a_n$ without loss of generality. Suppose that we may construct the needed tuples for $a_1,\dots ,a_{n-1}$, say $(c_{i,1},c_{i,2},\dots ,c_{i,n-1})$ with $1\le i\le M^{\prime }=\frac{1}{2^{n-1}}(a_1-1)a_2\dots a_n=\frac{2}{a_n}M$. Then it suffices to take $(c_{i,1},c_{i,2},\dots ,c_{i,n-1},2c)$ with $1\le i\le M^{\prime }$ and $1\le c\le \frac{a_n}{2}$.

Now it remains to prove for the case when all $a_2,a_3,\dots ,a_n$ are odd. Let us write $a_1=2^{n}t+1$ and consider the case when $a_1=a_2=\cdots =a_n$ first. In this case, $M=t{a}_1^{n-1}$. Define the function $f(x_1,x_2,\dots ,x_{n-1})={\sum }_{i=1}^{n-1}{2}^i{x}_i$ and take the following $M=t{a}_1^{n-1}$ tuples: $$(x_1,x_2,\dots ,x_{n-1},f(x_1,\dots ,x_{n-1})+2^{n}s),$$ where $x_1,\dots ,x_{n-1}\in \{1,2,\dots ,a_1\},s\in \{1,\dots ,t\}$. We now show that these tuples satisfy the desired conditions. Consider the above tuple together with another one: $(x_1^{\prime },x_2^{\prime },\dots ,x_{n-1}^{\prime },f(x_1^{\prime },\dots ,x_{n-1}^{\prime })+2^n{s}^{\prime })$. If for every $k$, the difference between their $k$th coordinate $\equiv 0,\pm 1(\mathrm{mod}{a}_1)$, then $$x_i-x_i^{\prime }\equiv 0,\pm 1(\mathrm{mod}{a}_1),i=1,\dots ,n-1;\text{ and}$$ $$\sum _{i=1}^{n-1}{2}^{i-1}(x_i-x_i^{\prime })+2^n(s-s^{\prime })\equiv 0,\pm 1(\mathrm{mod}{a}_1).(\ast )$$ The first equality implies that ${\sum }_{i=1}^{n-1}{2}^i(x_i-x_i^{\prime })$ can be only congruent to $2^{n-1}-1,2^{n-2}-1,\dots ,1-2^{n-1}(\mathrm{mod}{a}_1)$. On the other hand, $s-s^{\prime }\in \{1-t,2-t,\dots ,t-1\}$. So $s$ is forced to be equal to $s^{\prime }$ by $(\ast )$, and ${\sum }_{i=1}^{n-1}{2}^{i-1}(x_i-x_i^{\prime })=0(\mathrm{mod}{a}_1)$. By the uniqueness of binary expansion, we get $x_i=x_i^{\prime }(\mathrm{mod}{a}_1)$, which implies that the two tuples are the same. This verifies that the constructed tuples satisfy the needed conditions.

For the general case where $a_1,\dots ,a_n$ are all odd numbers, we claim that if $a_2>a_1$, the construction can be reduced to the case with $a_1,a_2-2,a_3,\dots ,a_n$. Hence by induction, it suffices to consider the case where all $a_i$ are equal, which is discussed above.

Assume now there exist $M^{\prime }=\frac{1}{2^n}(a_1-1)(a_2-2)a_3\cdots a_n$ tuples as desired when $a_1^{\prime }=a_1,a_2^{\prime }=a_2-2,a_3^{\prime }=a_3,\dots ,a_n^{\prime }=a_n$. We may assume that for each $k$, the $k$th coordinates of all these tuples belong the set $\{0,1,\dots ,a_k^{\prime }-1\}$.

We then define the $M=\frac{1}{2^n}(a_1-1)a_2{a}_3\cdots a_n$ tuples as follows. One can first choose the $M^{\prime }$ tuples that are already defined. As for $x_2=a_2-2$, we choose to add the tuple $(x_1,a_2-2,x_3,\dots ,x_n)$ if and only if the tuple $(x_1,a_2-4,x_3,\dots ,x_n)$ was selected; and for $x_2=a_2-1$, we choose to add the tuple $(x_1,a_2-1,x_3,\dots ,x_n)$ if and only if the tuple $(x_1,a_2-3,x_3,\dots ,x_n)$ was selected. It is easy to check that these tuples satisfy our requirement. Also, using the proof for $2^r|a_1-1$ by induction, the condition for equality implies the following: Among the $M^{\prime }$ tuples we have selected before, the number of tuples whose second coordinate is either $a_2-1$ or $a_2-2$ is $M^{\prime }\cdot \frac{2}{a_2-2}$. Hence we can the number of new tuples is $M^{\prime }+M^{\prime }\cdot \frac{2}{a_2-2}=M$. This completes the construction of the tuples.