2019 USAJMO Problems/Problem 1

Problem

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.

Solution

Claim: If $a$ and $b$ are both odd, then the end goal of achieving $b$ pears followed by $a$ apples is impossible.

Proof: Let $A_1$ and $P_1$ denote the number of apples and the number of pears in odd-numbered positions, respectively. We show that $A_1 - P_1$ is invariant. Notice that if $i$ and $j$ are odd, then $A_1$ and $P_1$ both decrease by 1, as one apple and one pear are both moved from odd-numbered positions to even-numbered positions. If $i$ and $j$ are even, then $A_1$ and $P_1$ both increase by 1.

Because the starting configuration $aa\ldots ab\ldots b$ has $\left\lfloor \frac{a}{2} \right\rfloor + 1$ odd-numbered apples and $\left\lfloor \frac{b}{2} \right\rfloor$ odd-numbered pears, the initial value of $A_1 - P_1$ is $\left\lfloor \frac{a}{2} \right\rfloor - \left\lfloor \frac{b}{2} \right\rfloor + 1$ . But the desired ending configuration has $\left\lfloor \frac{b}{2}\right\rfloor + 1$ odd-numbered pears and $\left\lfloor \frac{a}{2} \right\rfloor$ odd-numbered apples, so $A_1 - P_1 = \left\lfloor \frac{a}{2} \right\rfloor - \left\lfloor \frac{b}{2} \right\rfloor - 1$ . As $A_1 - P_1$ is invariant, it is impossible to attain the desired ending configuration. $\blacksquare$

Claim: If at least one of $a$ and $b$ is even, then the end goal of achieving $b$ pears followed by $a$ apples is possible.

Proof: Without loss of generality, assume $a$ is even. If only $b$ is even, then we can number the bowls in reverse, and swap apples with pears. We use two inductive arguments to show that $(a,b) = (2,b)$ is achievable for all $b\ge 1$ , then to show that $(a,b)$ is achievable for all even $a$ and all $b\ge 1$ .

Base case: $(a,b) = (2,1)$ . Then we can easily achieve the ending configuration in two moves, by moving the apple in bowl #1 and the pear in bowl #3 so that everything is in bowl #2, then finishing the next move.

Inductive step: suppose that for $a \ge 2$ (even) apples and $b \ge 1$ pears, that with $a$ apples and $b$ pears, the ending configuration is achievable. We will show two things: i) achievable with $a$ apples and $b+1$ pears, and ii) achievable with $a+2$ apples and $b$ pears.

i) Apply the process on the $a$ apples and first $b$ pairs to get a configuration $bb\ldots ba\ldots ab$ . Now we will "swap" the leftmost apple with the last pear by repeatedly applying the move on just these two fruits (as $a$ is even, the difference $i-j$ is even). This gives a solution for $a$ apples and $b+1$ pears. In particular, this shows that $(a,b) = (2,b)$ for all $b\ge 1$ is achievable.

ii) To show $(a+2, b)$ is achievable, given that $(a,b)$ is achievable, apply the process on the last $a$ apples and $b$ pears to get the configuration $aabbb\ldots baaa\ldots a$ . Then, because we have shown that 2 apples and $b$ pears is achievable in i), we can now reverse the first two apples and $b$ pears.

Thus for $ab$ even, the desired ending configuration is achievable. $\blacksquare$

Combining the above two claims, we see that this is possible if and only if $ab$ is even. -scrabbler94

Solution 2

"If" part: Note that two opposite fruits can be switched if they have even distance. If one of $a$ , $b$ is odd and the other is even, then switch $1$ with $a+b$ , $2$ with $a+b-1$ , $3$ with $a+b-2$ ... until all of one fruit is switched. If both are even, then if $a>b$ , then switch $1$ with $a+1$ , $2$ with $a+2$ , $3$ with $a+3$ ... until all of one fruit is switched; if $a<b$ then switch $a$ with $a+b$ , $a-1$ with $a+b-1$ , $a-2$ with $a+b-2$ ... until all of one fruit is switched. Each of these processes achieve the end goal.

"Only if" part: Assign each apple a value of $1$ and each pear a value of $-1$ . At any given point in time, let $E$ be the sum of the values of the fruit in even-numbered bowls. Because $a$ and $b$ both are odd, at the beginning there are $\frac{a-1}{2}$ apples in even bowls and $\frac{b+1}{2}$ pears in even bowls, so at the beginning $E=\frac{a-b}{2}-1$ . After the end goal is achieved, there are $\frac{a+1}{2}$ apples in even bowls and $\frac{b-1}{2}$ pears in even bowls, so after the end goal is achieved $E=\frac{a-b}{2}+1$ . However, because two opposite fruits must have the same parity to move and will be the same parity after they move, we see that $E$ is invariant, which is a contradiction; hence, it is impossible for the end goal to be reached if $ab$ is odd.

ayyo mathleticguyyy ur hot -Andrew Yuan

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

2019 USAJMO (Problems • Resources)
First Problem	Followed by Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions

Page

Toolbox

Search

2019 USAJMO Problems/Problem 1

Contents

Problem

Solution

Solution 2

See also