2019 USAJMO #1

There are $a+b$ bowls arranged in a row, numbered $1$ through $a+b$, where $a$ and $b$ are given positive integers. Initially, each of the first $a$ bowls contains an apple, and each of the last $b$ bowls contains a pear. A legal move consists of moving an apple from bowl $i$ to bowl $i+1$ and a pear from bowl $j$ to bowl $j-1$, provided that the difference $i-j$ is even. We permit multiple fruits in the same bowl at the same time. The goal is to end up with the first $b$ bowls each containing a pear and the last $a$ bowls each containing an apple. Show that this is possible if and only if the product $ab$ is even.

Claim: The number of moves required to have the first $b$ bowls each containing a pear and last $a$ bowls each containing an apple is exactly $ab$. 

Proof: Let $A$ be the sum of the positions of the apples and let $P$ be the sum of the positions of the pairs. Clearly, $A - P$ is incremented by $2$ at every move. We evalute the starting and ending values of $A - P$. The top one is the initial, while the bottom one is the final. \[A - P = \sum_{k = 1}^a - \sum_{k = a+1}^{a+b} = \frac{a(a+1)}{2} - \frac{b(2a + b - 1)}{2}\]\[A - P = \sum_{k = b+1}^{a+b} - \sum_{k = 1}^b = \frac{a(2b + a + 1)}{2} - \frac{b(b+1)}{2}\]so we find that $A-P$ has changed by $2ab$. This implies that the total number of moves is $\frac{2ab}{2}=ab$, as desired by the claim. 

We now prove that $ab$ is even. At each and every step, we look at the sum of the squares of the position of each fruit. When an apple goes from $i$ to $i+1$ and a pear goes from $j$ to $j-1$, the sum of the squares is altered by $$(i+1)^2+(j+1)^2-(i^2+j^2)=2(i-j)+2.$$

Because $i-j$ is even, $2(i-j)+2 \equiv 2 \pmod{4}$. As the sum of the squares of the positions of the fruits needs to stay same at the end of the process as it is at the beginning, the sum of these alterations is $0$. And because the sum of an odd number of integers congruent to $2 \pmod{4}$ is congruent to $2 \pmod{4}$, the total number of moves must be two more than a multiple of 4, which is even. We have proved that $ab$ is even. 

However, we are not done yet. We need to show the if condition as well. Note that $AAP$ can be transformed into $PAA$. We know that either $a$ or $b$ is even, as we proved $ab \equiv 0 \pmod{2}$.  Without loss of generality, assume $a$ is even. Because of the possible transformation $AAP \Rightarrow PAA$, we can move consecutive pairs of apples up the line of bowls every time. Repeatedly doing this will result in achieving the required condition of the problem. 

We have now proved both the "if" and "only if" parts, so we are done. $\square$