Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

Revision as of 20:47, 19 April 2019

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+3$, $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.

-Stormersyle

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

See also

2019 USAJMO (Problems • Resources)
First Problem Followed by
Problem 2
1 • 2 • 3 • 4 • 5 • 6
All USAJMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_USAJMO_Problems/Problem_1&oldid=105394"