Difference between revisions of "2019 USAJMO Problems/Problem 1"
m (→Problem) |
Aaryabhatta1 (talk | contribs) |
||
(2 intermediate revisions by one other user not shown) | |||
Line 35: | Line 35: | ||
Stormersyle | Stormersyle | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | We define a cycle to be when <math>2</math> fruits in bowls <math>i</math> and <math>j</math> are swapped with eachother, provided that bowls <math>i</math> contains an apple, bowl <math>j</math> contains a pear, and the difference <math>i-j</math> 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 <math>i+1</math> and the pear moves to bowl <math>j-1</math> at the beginning) using only valid moves. By a simple parity argument(if <math>k</math> moves have already been done, <math>i+k-(j-k)=i+j+2k=0+2k=2k=0 \textbf{mod 2}</math>), these moves are always valid, so we are done. <math>\blacksquare</math> | ||
+ | |||
+ | We now split the "if" part of this proof into cases based on the parities of <math>a</math> and <math>b</math>. | ||
+ | |||
+ | Case 1: <math>a</math> even, <math>b</math> odd | ||
+ | In this case we can simply cycle the fruit in bowl <math>k+1</math> with the fruit in bowl <math>a+b-k</math> for all integer <math>k</math> in the range <math>[0,b-1]</math> to achieve our desired goal. The difference <math>a+b-k-k-1=a+b-1</math> is even, so the move is valid. | ||
+ | |||
+ | Case 2: <math>b</math> even, <math>a</math> odd | ||
+ | Using the same cycle as the previous case works here. | ||
+ | |||
+ | Case 3: <math>a</math> even, <math>b</math> even | ||
+ | Here, we can cycle the fruits in bowls <math>k</math> and <math>a+b-k</math> for all integer <math>k</math> in the range <math>[1,b]</math>. Then, we finish by cycling the fruits in bowls <math>a</math> and <math>a+b</math>. 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 <math>A_1</math>, and the number of pears in odd positions be <math>A_2</math>. Obviously <math>A_1-A_2</math> is invariant when using valid moves only. We can now use proof by contradiction(i.e. showing that this invariant does not occur when <math>a, b \equiv 1 \text{ mod } 2</math> and our desired goal is achieved) to find that we have that <math>0=2</math>, 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. <math>\blacksquare</math> | ||
+ | |||
+ | ~smartninja2000 | ||
+ | |||
+ | ==Solution 4== | ||
+ | |||
+ | Begin by defining a <math>\textit{swap}</math> as a set of <math>i - j</math> legal moves taking an apple in <math>i \rightarrow j</math> and the pear in <math>j \rightarrow i</math>. Now we begin by proving if <math>ab</math> is even, then the final configuration is possible. | ||
+ | |||
+ | WLOG let <math>b</math> be even. Then there are two cases to consider. <math>a < b, a \ge b</math> to provide valid constructions for. In the first case, consider the apple/pear pairs <math>(1,b+1), (2, b+2), \dots, (i, b+i), \dots, (a, b+a)</math> and swap them. This results in the transformation, | ||
+ | <cmath>\begin{align*} | ||
+ | \underbrace{AA \cdots A}_{\text{a apples}}& \underbrace{PP \cdots P}_{\text{b pears}} \ | ||
+ | \underbrace{PP \cdots P}_{\text{a pears}}& \underbrace{PP \cdots P}_{\text{b-a pears}} \underbrace{AA \cdots A}_{\text{a apples}} \ | ||
+ | \underbrace{PP \cdots P}_{\text{b pears}} &\underbrace{AA \cdots A}_{\text{a apples}} \ | ||
+ | \end{align*} </cmath> | ||
+ | as desired. | ||
+ | |||
+ | Now consider the case where <math>a \ge b</math>. Also consider the pairing, <math>(a-b + 1, a + 1), (a - b + 2, a+2), \dots, (a - b + i, a+i), \dots, (a, a + b)</math> and swap them. This results in the transformation, | ||
+ | <cmath>\begin{align*} | ||
+ | \underbrace{AA \cdots A}_{\text{a apples}} & \underbrace{PP \cdots P}_{\text{b pears}} \ | ||
+ | \underbrace{AA \cdots A}_{\text{a-b apples}}\underbrace{PP \cdots P}_{\text{b pears}}& \underbrace{AA \cdots A}_{\text{b apples}}. | ||
+ | \end{align*}</cmath> | ||
+ | Now just consider the leftmost <math>a</math> bowls. There are <math>a-b</math> apples, and then <math>b</math> pears. We have effectively reduced <math>(a,b) \rightarrow (a-b, b)</math>. Reducing in this fashion recursively will lead to <math>(a \pmod{b}, b)</math> which can be constructed with the <math>a<b</math> case. This finishes the construction for <math>a \ge b</math>. | ||
+ | |||
+ | Now assume <math>ab,a,b</math> are odd. FTSOC, let this case satisfy the claim. Then, for each apple, define it's <math>\textit{position}</math> as the sum of the distance from it to all other pairs. So for apple in bowl <math>i \le a</math> originally, the position of <math>i</math> is <math>\sum_{j = a+1}^{b} j - i .</math> | ||
+ | |||
+ | Every time a legal move is made, the position of the apple decreases by <math>b - 1 + 2 = b+1</math> (from the <math>b-1</math> pears not part of the move and the decrease in <math>2</math> by the corresponding pear). Also note that there needs to be exactly <math>ab</math> moves in order to attain the final configurations. So the difference in sum of positions of the apples at the beginning and end is <math>ab(b+1)</math>. Mathematically, | ||
+ | <cmath>\begin{align*} | ||
+ | \sum_{i = 1}^{a} \sum_{j = a+1}^{a+b} j - i - \sum_{i = b + 1}^{b+a} \sum_{j = 1}^{b} j - i &= ab(b+1)\ | ||
+ | (\frac{ab(2a + b + 1)}{2} - \frac{ab(a + 1)}{2}) - (\frac{ab(b+1)}{2} - \frac{ab(a + 2b + 1)}{2}) &= \ | ||
+ | ab(a+b) &= ab(b+1) \ | ||
+ | a &= 1. | ||
+ | \end{align*}</cmath> | ||
+ | A symmetric argument for the position of pears gives <math>b = 1</math>. Clearly the <math>a=b=1</math> does not have a solution, therefore we have contradiction. <math>\square</math> | ||
+ | |||
+ | ~ Aaryabhatta1 | ||
+ | |||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 16:44, 4 September 2022
Problem
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.
Solution
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
Solution 2
"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.
Stormersyle
Solution 3
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.
~smartninja2000
Solution 4
Begin by defining a as a set of
legal moves taking an apple in
and the pear in
. Now we begin by proving if
is even, then the final configuration is possible.
WLOG let be even. Then there are two cases to consider.
to provide valid constructions for. In the first case, consider the apple/pear pairs
and swap them. This results in the transformation,
as desired.
Now consider the case where . Also consider the pairing,
and swap them. This results in the transformation,
Now just consider the leftmost
bowls. There are
apples, and then
pears. We have effectively reduced
. Reducing in this fashion recursively will lead to
which can be constructed with the
case. This finishes the construction for
.
Now assume are odd. FTSOC, let this case satisfy the claim. Then, for each apple, define it's
as the sum of the distance from it to all other pairs. So for apple in bowl
originally, the position of
is
Every time a legal move is made, the position of the apple decreases by (from the
pears not part of the move and the decrease in
by the corresponding pear). Also note that there needs to be exactly
moves in order to attain the final configurations. So the difference in sum of positions of the apples at the beginning and end is
. Mathematically,
A symmetric argument for the position of pears gives
. Clearly the
does not have a solution, therefore we have contradiction.
~ Aaryabhatta1
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.
See also
2019 USAJMO (Problems • Resources) | ||
First Problem | Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAJMO Problems and Solutions |