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 29: Line 29:
 
==Solution 2==
 
==Solution 2==
 
"If" part:
 
"If" part:
−
 
 
Note that two opposite fruits can be switched if they have even distance. If one of <math>a</math>, <math>b</math> is odd and the other is even, then switch <math>1</math> with <math>a+b</math>, <math>2</math> with <math>a+b-1</math>, <math>3</math> with <math>a+b-2</math>... until all of one fruit is switched. If both are even, then if <math>a>b</math>, then switch <math>1</math> with <math>a+1</math>, <math>2</math> with <math>a+3</math>, <math>3</math> with <math>a+3</math>... until all of one fruit is switched; if <math>a<b</math> then switch <math>a</math> with <math>a+b</math>, <math>a-1</math> with <math>a+b-1</math>, <math>a-2</math> with <math>a+b-2</math>... until all of one fruit is switched. Each of these processes achieve the end goal.
 
Note that two opposite fruits can be switched if they have even distance. If one of <math>a</math>, <math>b</math> is odd and the other is even, then switch <math>1</math> with <math>a+b</math>, <math>2</math> with <math>a+b-1</math>, <math>3</math> with <math>a+b-2</math>... until all of one fruit is switched. If both are even, then if <math>a>b</math>, then switch <math>1</math> with <math>a+1</math>, <math>2</math> with <math>a+3</math>, <math>3</math> with <math>a+3</math>... until all of one fruit is switched; if <math>a<b</math> then switch <math>a</math> with <math>a+b</math>, <math>a-1</math> with <math>a+b-1</math>, <math>a-2</math> with <math>a+b-2</math>... until all of one fruit is switched. Each of these processes achieve the end goal.
  

Revision as of 20:46, 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, and let $O$ be the sum of the values of the fruit in odd-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=105393"