2022 China Team Selection Test for IMO

Proof: The smallest positive integer $M$ is $p^a{q}^b{r}^c$.

First, if we initially put less than $p^a{q}^b{r}^c$ stones at the point $(a,b,c)$, then one cannot perform a sequence of operations to put a stone at $(0,0,0)$. The reason is as follows. For a stone $u$ at $(x,y,z)$, define its weight as $w(u)=\frac{1}{p^x{q}^y{r}^z}$. The rules of operation ensures that the total weight of all stones $W=\sum w(u)$ stays unchanged. If initially, there are less than $p^a{q}^b{r}^c$ stones at $(a,b,c)$, then $W<1$. Hence at any moment there is no stone at $(0,0,0)$.

Conversely, we will prove an $n$-dimension version of this problem. Let $a_1,\dots ,a_n$ and $p_1,\dots ,p_n$ be positive integers, such that $2\le p_1\le \cdots \le p_n$. Consider the same game on an $n$-dimensional lattice $$Q(a_1,\dots ,a_n)=\{(x_1,\dots ,x_n)\in {\mathbb{Z}}^n\mid 0\le x_i\le a_i,i=1,\dots ,n\}$$ We initially put total $M$ stones on $Q(a_1,\dots ,a_n)$. For $i=1,2,\dots ,n$, we call the operation which removes $p_i$ stones at one point $(x_1,\dots ,x_n)$ and then put one stone at $(x_1,\dots ,x_i-1,\dots ,x_n)$ as “operation $X_i$”. We will need another type of operation $T_q$: which removes $q$ stones at a point but do not put back any stones. We make a convention that when $n=0$, $Q=\{0\}$ is one pointed set containing only the original point.

Let $M$ denote the total number of stones on $Q(a_1,\dots ,a_n)$ by $M$, and let $K$ denote the number of the lattice points where at least one stone is placed. Denote the values of $M$ and $K$ of the domain $\mathbf{I}:Q(a_1,\dots ,a_n-1)$ as $M_1$ and $K_1$, respectively; and denote the value of $M$ and $K$ of domain $\mathbf{II}$: $$Q(a_1,\dots ,a_{n-1})\times \{a_n\}=Q(a_1,\dots ,a_n)\setminus Q(a_1,\dots ,a_n-1)$$ as $M_2$ and $K_2$ respectively. In the following proof, an important step is to do as many as possible operation $X_n$ for stones in domain $\mathbf{II}$ to “transfer” them into domain $\mathbf{I}$, until

stones in the domain II can not do anymore operation $X_n$. At that moment, at each point of domain II which has at least one stone can hold at most $p_n-1$ stones, thus we can transfer at least $\frac{M_2-(p_n-1)K_2}{p_n}$ stones to domain I. Call these operations as “transfer II to I”.

We are going to inductively prove following three propositions:

Proposition A(n): If $M=p_1^{a_1}\cdots p_n^{a_n}$, then one can perform a sequence operations $X_1,\dots ,X_n$ to move a stone to the origin 0.

Proposition B(n): Let $u\ge 2$ be a positive integer. If $M+K>u\cdot p_1^{a_1}\cdots p_n^{a_n}$, then one can perform a sequence operations $X_1,\dots ,X_n$ to move $u$ stones to the origin 0.

Proposition C(n): Assume that $q\ge p_n$, $s$ is a positive integer, and $t$ is a nonnegative integer. If $M+K>sq\cdot p_1^{a_1}\cdots p_n^{a_n}+t$, then one can first perform $\lfloor \frac{t}{q}\rfloor$ times operation $T_q$, and after that perform a sequence operations $X_1,\dots ,X_n$ to move $sq$ stones to origin 0.

We do an induction on $n$. Propositions $A(0),B(0),C(0)$ are obvious. Suppose that $A(n-1),B(n-1),C(n-1)$ are proved. We aim to prove Propositions $A(n),B(n),C(n)$ by an induction on $a_n$. When $a_n=0$, $Q(a_1,\dots ,a_n)=Q(a_1,\dots ,a_{n-1})\times \{0\}$, then $A(n),B(n),C(n)$ for $Q(a_1,\dots ,a_n)$ corresponds to $A(n-1),B(n-1),C(n-1)$ for $Q(a_1,\dots ,a_{n-1})$; this is already known. So we may assume that $a_n\ge 1$.

The proof of Proposition A(n).

a.1) If $M_1\ge K_2$, Using transfer II to I, one may at least transfer $\frac{M_2-(p_n-1)K_2}{p_n}$ stones, after that we have $$M_1^{\prime }\ge M_1+\frac{M_2-(p_n-1)K_2}{p_n}=p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n}+\frac{(p_n-1)(M_1-K_2)}{p_n}\ge p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n},$$ By inductive hypothesis, we may place a stone at 0.

a.2) If $M_1<K_2$, then $M_2+K_2>M_2+M_1=p_n^{a_n}\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}$. Note that $p_n^{a_n}\ge 2$. Using $B(n-1)$, we know that we can move $p_n^{a_n}$ stones from II to $(0,\dots ,0,a_n)$, then perform $a_n$ times operation $X_n$ to get one stone at 0.

The proof of Proposition B(n).

b.1) If $M_1+K_1\ge \frac{p_n}{p_{n-1}}{K}_2$, we may transfer at least $\frac{M_2-(p_n-1)K_2}{p_n}$ stones from II to I. After that we have $$\begin{array}{rl}{M}_1^{\prime }+K_1^{\prime }& \ge M_1+K_1+\frac{M_2-(p_n-1)K_2}{p_n}>M_1+K_1+\frac{u\cdot p_1^{a_1}\cdots p_n^{a_n}-M_1-K_1-p_n{K}_2}{p_n}\\ & =u\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n}+\frac{(p_n-1)(M_1+K_1)-p_n{K}_2}{p_n}\ge u\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n},\end{array}$$ The inductive hypothesis implies that we can move $u$ stones to 0.

b.2) If $M_1+K_1<\frac{p_n}{p_{n-1}}{K}_2$, then Bernoulli's inequality implies that $$M_1+K_1<\frac{p_n}{p_n-1}{K}_2\le 2(1+a_1)\cdots (1+a_{n-1})\le p_n^{a_n}{p}_1^{a_1}\cdots p_{n-1}^{a_{n-1}},$$

i.e. $p_1^{a_1}\cdots p_n^{a_n}-M_1-K_1$ is nonnegative. Note that $M_2+K_2>u\cdot p_1^{a_1}\cdots p_n^{a_n}-(M_1+K_1)=(u-1)p_n^{a_n}\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}+(p_1^{a_1}\cdots p_n^{a_n}-M_1-K_1)$, and we have $u-1\ge 1$ and $p_n\ge p_{n-1}$. Using $C(n-1)$, we may perform $\lfloor \frac{p_1^{a_1}\cdots p_n^{a_n}-M_1-K_1}{p_n}\rfloor$ times $T_{p_n}$ in $\mathbf{II}$, and then move $(u-1)p_n^{a_n}$ stones to $(0,\dots ,0,a_n)$. These $(u-1)p_n^{a_n}$ stones can be moved to $u-1$ stone at $0$ by operation $X_n$. On the other hand, the stones from the $\lfloor \frac{p_1^{a_1}\cdots p_n^{a_n}-M_1-K_1}{p_n}\rfloor$ times operation $T_{p_n}$ can be used to perform operation $X_n$ to get $\lfloor \frac{p_1^{a_1}\cdots p_n^{a_n}-M_1-K_1}{p_n}\rfloor$ stones in domain $\mathbf{I}$. After that, in $\mathbf{I}$ we have $$\begin{array}{rl}{M}_1^{\prime }& \ge M_1+\lfloor \frac{p_1^{a_1}\cdots p_n^{a_n}-M_1-K_1}{p_n}\rfloor \\ & =p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n}+\lfloor \frac{(p_n-1)M_1-K_1}{p_n}\rfloor \ge p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n},\end{array}$$ Use the already proved Proposition A(n), we may get one more stone at 0. Combine these two parts, we obtain u stones at 0.

The proof of Proposition C(n).

c.1) If $t<q$, we do not need do operation $T_q$. Note that $sq\ge 2$ and $M+K>sq\cdot p_1^{a_1}\cdots p_n^{a_n}$. Use the proved Proposition B(n) we can move $sq$ stones to 0.

c.2) If $t\ge q$, we need to do some operation $T_q$. If some place in domain II has more than q stones, we do an operation $T_q$ at that point, then $M^{\prime }=M-q$ and $K^{\prime }=K$; moreover, it becomes the case $t^{\prime }=t-q$. After some operation $T_q$, we either arrive at the case $t<q$ which is (c.1), or at every point of II, the number of stones is less than or equal to q. It suffices to deal with the latter situation. Assume that II has L points which has exactly q stones. The Bernoulli's inequality gives $$\begin{array}{rl}{M}_1+K_1& =M+K-(M_2+K_2)>sq\cdot p_1^{a_1}\cdots p_n^{a_n}+t-(q(K_2-L)+(q+1)L)\\ & =sq\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n}+t+(sq\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n})(p_n-1)-q{K}_2-L)\\ & \ge sq\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n}+t+(q(1+a_1)\cdots (1+a_{n-1})-q{K}_2-L)\\ & \ge sq\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n}+t-L.\end{array}$$ Since $q\ge p_n$, we can do operation $X_n$ once again at the $L$ points which has exactly $q$ stones in $\mathbf{II}$. After that, $$M_1^{\prime }+K_1^{\prime }\ge M_1+K_1+L>sq\cdot p_1^{a_1}\cdots p_{n-1}^{a_{n-1}}{p}_n^{a_n}+t,$$ Using the inductive hypothesis for domain I, we know that we can do $\lfloor \frac{t}{q}\rfloor$ times $T_q$, and then move $sq$ stones to 0.

This completes the induction.