2019 USAJMO Problems/Problem 1
There are bowls arranged in a row, numbered through , where and are given positive integers. Initially, each of the first bowls contains an apple, and each of the last bowls contains a pear.
A legal move consists of moving an apple from bowl to bowl and a pear from bowl to bowl , provided that the difference is even. We permit multiple fruits in the same bowl at the same time. The goal is to end up with the first bowls each containing a pear and the last bowls each containing an apple. Show that this is possible if and only if the product is even.
Claim: If and are both odd, then the end goal of achieving pears followed by apples is impossible.
Proof: Let and denote the number of apples and the number of pears in odd-numbered positions, respectively. We show that is invariant. Notice that if and are odd, then and both decrease by 1, as one apple and one pear are both moved from odd-numbered positions to even-numbered positions. If and are even, then and both increase by 1.
Because the starting configuration has odd-numbered apples and odd-numbered pears, the initial value of is . But the desired ending configuration has odd-numbered pears and odd-numbered apples, so . As is invariant, it is impossible to attain the desired ending configuration.
Claim: If at least one of and is even, then the end goal of achieving pears followed by apples is possible.
Proof: Without loss of generality, assume is even. If only is even, then we can number the bowls in reverse, and swap apples with pears. We use two inductive arguments to show that is achievable for all , then to show that is achievable for all even and all .
Base case: . 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 (even) apples and pears, that with apples and pears, the ending configuration is achievable. We will show two things: i) achievable with apples and pears, and ii) achievable with apples and pears.
i) Apply the process on the apples and first pairs to get a configuration . Now we will "swap" the leftmost apple with the last pear by repeatedly applying the move on just these two fruits (as is even, the difference is even). This gives a solution for apples and pears. In particular, this shows that for all is achievable.
ii) To show is achievable, given that is achievable, apply the process on the last apples and pears to get the configuration . Then, because we have shown that 2 apples and pears is achievable in i), we can now reverse the first two apples and pears.
Thus for even, the desired ending configuration is achievable.
Combining the above two claims, we see that this is possible if and only if is even. -scrabbler94
"If" part: Note that two opposite fruits can be switched if they have even distance. If one of , is odd and the other is even, then switch with , with , with ... until all of one fruit is switched. If both are even, then if , then switch with , with , with ... until all of one fruit is switched; if then switch with , with , with ... until all of one fruit is switched. Each of these processes achieve the end goal.
"Only if" part: Assign each apple a value of and each pear a value of . At any given point in time, let be the sum of the values of the fruit in even-numbered bowls. Because and both are odd, at the beginning there are apples in even bowls and pears in even bowls, so at the beginning . After the end goal is achieved, there are apples in even bowls and pears in even bowls, so after the end goal is achieved . However, because two opposite fruits must have the same parity to move and will be the same parity after they move, we see that is invariant, which is a contradiction; hence, it is impossible for the end goal to be reached if is odd.
We define a cycle to be when fruits in bowls and are swapped with eachother, provided that bowls contains an apple, bowl contains a pear, and the difference is even.
We claim that a cycle consists of only the valid moves described in the problem statement. Proof: We can move the apple and pear one step at a time to eventually reach the other's bowl(i.e. the apple moves to and the pear moves to bowl at the beginning) using only valid moves. By a simple parity argument(if moves have already been done, ), these moves are always valid, so we are done.
We now split the "if" part of this proof into cases based on the parities of and .
Case 1: even, odd In this case we can simply cycle the fruit in bowl with the fruit in bowl for all integer in the range to achieve our desired goal. The difference is even, so the move is valid.
Case 2: even, odd Using the same cycle as the previous case works here.
Case 3: even, even Here, we can cycle the fruits in bowls and for all integer in the range . Then, we finish by cycling the fruits in bowls and . These are both valid moves by similar parity arguments as done in Case 1.
Since we have exhausted all possible cases for the "if" part of this proof, we have completed the if part. We will proceed with the "only if" part.
We let the number of apples in odd positions be , and the number of pears in odd positions be . Obviously is invariant when using valid moves only. We can now use proof by contradiction(i.e. showing that this invariant does not occur when and our desired goal is achieved) to find that we have that , which is obviously false, so we have completed the proof for the "only if" part.
We are now done, since we have completed our proofs for the "if" and "only if" parts.
|2019 USAJMO (Problems • Resources)|
|First Problem||Followed by|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAJMO Problems and Solutions|