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"

m (→‎Problem)
(→‎Solution: add solution)
Line 5: Line 5:
  
 
==Solution==
 
==Solution==
 +
<b>Claim:</b> If <math>a</math> and <math>b</math> are both odd, then the end goal of achieving <math>b</math> pears followed by <math>a</math> apples is impossible.
 +
 +
<b>Proof:</b> Let <math>A_1</math> and <math>P_1</math> denote the number of apples and the number of pears in odd-numbered positions, respectively. We show that <math>A_1 - P_1</math> is invariant. Notice that if <math>i</math> and <math>j</math> are odd, then <math>A_1</math> and <math>P_1</math> both decrease by 1, as one apple and one pear are both moved from odd-numbered positions to even-numbered positions. If <math>i</math> and <math>j</math> are even, then <math>A_1</math> and <math>P_1</math> both increase by 1.
 +
 +
Because the starting configuration <math>aa\ldots ab\ldots b</math> has <math>\left\lfloor \frac{a}{2} \right\rfloor + 1</math> odd-numbered apples and <math>\left\lfloor \frac{b}{2} \right\rfloor</math> odd-numbered pears, the initial value of <math>A_1 - P_1</math> is <math>\left\lfloor \frac{a}{2} \right\rfloor - \left\lfloor \frac{b}{2} \right\rfloor + 1</math>. But the desired ending configuration has <math>\left\lfloor \frac{b}{2}\right\rfloor + 1</math> odd-numbered pears and <math>\left\lfloor \frac{a}{2} \right\rfloor</math> odd-numbered apples, so <math>A_1 - P_1 = \left\lfloor \frac{a}{2} \right\rfloor - \left\lfloor \frac{b}{2} \right\rfloor - 1</math>. As <math>A_1 - P_1</math> is invariant, it is impossible to attain the desired ending configuration. <math>\blacksquare</math>
 +
 +
<b>Claim:</b> If at least one of <math>a</math> and <math>b</math> is even, then the end goal of achieving <math>b</math> pears followed by <math>a</math> apples is possible.
 +
 +
<b>Proof:</b> Without loss of generality, assume <math>a</math> is even. If only <math>b</math> is even, then we can number the bowls in reverse, and swap apples with pears. We use two inductive arguments to show that <math>(a,b) = (2,b)</math> is achievable for all <math>b\ge 1</math>, then to show that <math>(a,b)</math> is achievable for all even <math>a</math> and all <math>b\ge 1</math>.
 +
 +
<i>Base case:</i> <math>(a,b) = (2,1)</math>. 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.
 +
 +
<i>Inductive step:</i> suppose that for <math>a \ge 2</math> (even) apples and <math>b \ge 1</math> pears, that with <math>a</math> apples and <math>b</math> pears, the ending configuration is achievable. We will show two things: i) achievable with <math>a</math> apples and <math>b+1</math> pears, and ii) achievable with <math>a+2</math> apples and <math>b</math> pears.
 +
 +
i) Apply the process on the <math>a</math> apples and first <math>b</math> pairs to get a configuration <math>bb\ldots ba\ldots ab</math>. Now we will "swap" the leftmost apple with the last pear by repeatedly applying the move on just these two fruits (as <math>a</math> is even, the difference <math>i-j</math> is even). This gives a solution for <math>a</math> apples and <math>b+1</math> pears. In particular, this shows that <math>(a,b) = (2,b)</math> for all <math>b\ge 1</math> is achievable.
 +
 +
ii) To show <math>(a+2, b)</math> is achievable, given that <math>(a,b)</math> is achievable, apply the process on the last <math>a</math> apples and <math>b</math> pears to get the configuration <math>aabbb\ldots baaa\ldots a</math>. Then, because we have shown that 2 apples and <math>b</math> pears is achievable in i), we can now reverse the first two apples and <math>b</math> pears.
 +
 +
Thus for <math>ab</math> even, the desired ending configuration is achievable. <math>\blacksquare</math>
 +
 +
Combining the above two claims, we see that this is possible if and only if <math>ab</math> is even. -scrabbler94
 +
 +
  
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 00:34, 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


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=105350"