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 "2000 USAMO Problems/Problem 3"
m (→‎Solution)
 
(6 intermediate revisions by 5 users not shown)
Line 4: Line 4:
  
 
== Solution ==
 
== Solution ==
−
{{solution}}
+
We claim (inductively) that the minimum is just going to be <math>\min(BW,2WR,3RB)</math>. We'll start our induction with the case where one of the three quantities is zero, in which case we verify that we can indeed get away without any penalty by, for example, discarding blue if we are out of white.
 +
 
 +
Now, for the inductive step, let <math>f(B,W,R)</math> be the minimum we seek. Note that
 +
<cmath>f(B,W,R) = \min(W+f(B-1,W,R),2R+f(B,W-1,R),3B+f(B,W,R-1)) </cmath>
 +
By our inductive hypothesis, <math>f(B-1,W,R) = \min((B-1)W,2WR,3R(B-1))</math>. In order for this to cause our inductive step not to hold, we would require that <math>W+\min((B-1)W,2WR,3R(B-1)) < \min(BW,2WR,3RB)</math>. It is evident that the first two entries in the <math>min</math> expression cannot cause this to happen, so that we need only consider <math>W+3R(B-1) < \min(BW,2WR,3RB)</math>. So <math>W+3R(B-1) < BW</math>, whence <math>3R < W</math>. But <math>W+3R(B-1) < 3RB</math>, so that <math>W < 3R</math>, a contradiction.
 +
 
 +
For the other two cases, we can get similar contradictions, so that our inductive step must hold, and so <math>f(B,W,R)</math> is indeed <math>\min(BW,2WR,3RB)</math>.
 +
 
 +
We now need only establish how many ways to do this. If one of these quantities is smaller, our induction and the fact that it is eventually zero guarantees that it will continue to be the smallest quantity as cards are discarded. (For example, if it is currently optimal to discard a blue card, it will continue to be so until we run out of blue cards.) Therefore, assuming that there is currently only one best choice of card to discard, this will continue to be so in the future, whence if <math>BW \neq 2WR \neq 3RB</math>, there is only <math>1</math> optimal strategy.
 +
 
 +
Suppose, now, that <math>BW = 2WR</math>. It is thus optimal to discard either a <math>B</math> or <math>W</math> card. If we ever discard a blue card, then we will cause <math>BW < 2WR</math>, whence there is only one possible strategy from then on. However, if we discard a white card, then we will still have <math>BW = 2WR</math>, meaning that we continue to have the choice of discarding a white or blue card. Since we can discard a white card at most <math>W</math> times, there are <math>W+1</math> choices for how many <math>W</math> cards to discard (<math>0</math> to <math>W</math>), meaning that there are <math>W+1</math> optimal strategies.
 +
 
 +
By similar logic, we get <math>R+1</math> optimal strategies if <math>2WR = 3RB</math>, and <math>B+1</math> optimal strategies if <math>3RB = BW</math>.
 +
 
 +
The final case, then, is if <math>BW = 2WR = 3RB</math>. In this case, if we first discard a white card, we are left with the <math>BW = 2WR</math> case, and similarly for a blue and red card. The total number of optimal strategies in this case is then the sum of the optimal strategies in those cases, or, in other words, <math>B+W+R</math>.
 +
 
 +
To summarize:
 +
The minimum penalty is <math>\min(BW,2WR,3RB)</math>.
 +
If <math>BW \neq 2WR \neq 3RB</math>, there is <math>1</math> optimal strategy.
 +
If <math>BW = 2WR < 3RB</math>, there are <math>W+1</math> strategies.
 +
If <math>2WR = 3RB < BW</math>, there are <math>R+1</math> strategies.
 +
If <math>3RB = BW < 2WR</math>, there are <math>B+1</math> strategies.
 +
If <math>BW = 2WR = 3RB</math>, there are <math>R+B+W</math> strategies.
 +
 
 +
By J Steinhardt, from AoPS Community
  
 
== See Also ==
 
== See Also ==
 
{{USAMO newbox|year=2000|num-b=2|num-a=4}}
 
{{USAMO newbox|year=2000|num-b=2|num-a=4}}
  
−
[[Category:Olympiad Algebra Problems]]
+
[[Category:Olympiad Combinatorics Problems]]
 +
{{MAA Notice}}

Latest revision as of 20:24, 28 August 2019

Problem

A game of solitaire is played with $R$ red cards, $W$ white cards, and $B$ blue cards. A player plays all the cards one at a time. With each play he accumulates a penalty. If he plays a blue card, then he is charged a penalty which is the number of white cards still in his hand. If he plays a white card, then he is charged a penalty which is twice the number of red cards still in his hand. If he plays a red card, then he is charged a penalty which is three times the number of blue cards still in his hand. Find, as a function of $R, W,$ and $B,$ the minimal total penalty a player can amass and all the ways in which this minimum can be achieved.

Solution

We claim (inductively) that the minimum is just going to be $\min(BW,2WR,3RB)$. We'll start our induction with the case where one of the three quantities is zero, in which case we verify that we can indeed get away without any penalty by, for example, discarding blue if we are out of white.

Now, for the inductive step, let $f(B,W,R)$ be the minimum we seek. Note that \[f(B,W,R) = \min(W+f(B-1,W,R),2R+f(B,W-1,R),3B+f(B,W,R-1))\] By our inductive hypothesis, $f(B-1,W,R) = \min((B-1)W,2WR,3R(B-1))$. In order for this to cause our inductive step not to hold, we would require that $W+\min((B-1)W,2WR,3R(B-1)) < \min(BW,2WR,3RB)$. It is evident that the first two entries in the $min$ expression cannot cause this to happen, so that we need only consider $W+3R(B-1) < \min(BW,2WR,3RB)$. So $W+3R(B-1) < BW$, whence $3R < W$. But $W+3R(B-1) < 3RB$, so that $W < 3R$, a contradiction.

For the other two cases, we can get similar contradictions, so that our inductive step must hold, and so $f(B,W,R)$ is indeed $\min(BW,2WR,3RB)$.

We now need only establish how many ways to do this. If one of these quantities is smaller, our induction and the fact that it is eventually zero guarantees that it will continue to be the smallest quantity as cards are discarded. (For example, if it is currently optimal to discard a blue card, it will continue to be so until we run out of blue cards.) Therefore, assuming that there is currently only one best choice of card to discard, this will continue to be so in the future, whence if $BW \neq 2WR \neq 3RB$, there is only $1$ optimal strategy.

Suppose, now, that $BW = 2WR$. It is thus optimal to discard either a $B$ or $W$ card. If we ever discard a blue card, then we will cause $BW < 2WR$, whence there is only one possible strategy from then on. However, if we discard a white card, then we will still have $BW = 2WR$, meaning that we continue to have the choice of discarding a white or blue card. Since we can discard a white card at most $W$ times, there are $W+1$ choices for how many $W$ cards to discard ($0$ to $W$), meaning that there are $W+1$ optimal strategies.

By similar logic, we get $R+1$ optimal strategies if $2WR = 3RB$, and $B+1$ optimal strategies if $3RB = BW$.

The final case, then, is if $BW = 2WR = 3RB$. In this case, if we first discard a white card, we are left with the $BW = 2WR$ case, and similarly for a blue and red card. The total number of optimal strategies in this case is then the sum of the optimal strategies in those cases, or, in other words, $B+W+R$.

To summarize: The minimum penalty is $\min(BW,2WR,3RB)$. If $BW \neq 2WR \neq 3RB$, there is $1$ optimal strategy. If $BW = 2WR < 3RB$, there are $W+1$ strategies. If $2WR = 3RB < BW$, there are $R+1$ strategies. If $3RB = BW < 2WR$, there are $B+1$ strategies. If $BW = 2WR = 3RB$, there are $R+B+W$ strategies.

By J Steinhardt, from AoPS Community

See Also

2000 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2000_USAMO_Problems/Problem_3&oldid=109468"