Difference between revisions of "2000 USAMO Problems/Problem 3"
Toinfinity (talk | contribs) m (→Solution) |
Caroline2023 (talk | contribs) m (→Solution) |
||
Line 7: | Line 7: | ||
Now, for the inductive step, let <math>f(R,W,B)</math> be the minimum we seek. Note that | Now, for the inductive step, let <math>f(R,W,B)</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, | + | <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. | 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. | ||
Revision as of 21:11, 27 August 2019
Problem
A game of solitaire is played with red cards,
white cards, and
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
and
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 . 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 be the minimum we seek. Note that
By our inductive hypothesis,
. In order for this to cause our inductive step not to hold, we would require that
. It is evident that the first two entries in the
expression cannot cause this to happen, so that we need only consider
. So
, whence
. But
, so that
, a contradiction.
For the other two cases, we can get similar contradictions, so that our inductive step must hold, and so is indeed
.
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 , there is only
optimal strategy.
Suppose, now, that . It is thus optimal to discard either a
or
card. If we ever discard a blue card, then we will cause
, whence there is only one possible strategy from then on. However, if we discard a white card, then we will still have
, meaning that we continue to have the choice of discarding a white or blue card. Since we can discard a white card at most
times, there are
choices for how many
cards to discard (
to
), meaning that there are
optimal strategies.
By similar logic, we get optimal strategies if
, and
optimal strategies if
.
The final case, then, is if . In this case, if we first discard a white card, we are left with the
case, and similarly for a blue and white 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,
.
To summarize:
The minimum penalty is .
If
, there is
optimal strategy.
If
, there are
strategies.
If
, there are
strategies.
If
, there are
strategies.
If
, there are
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.