Difference between revisions of "2000 USAMO Problems/Problem 3"
Caroline2023 (talk | contribs) m (→Solution) |
|||
(3 intermediate revisions by 2 users not shown) | |||
Line 4: | Line 4: | ||
== 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. | + | 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( | + | 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, | + | <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. |
− | 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>. | + | 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. | 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. | ||
Line 18: | Line 18: | ||
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>. | 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 | + | 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: | To summarize: | ||
− | The minimum penalty is <math>min(BW,2WR,3RB)</math>. | + | 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 \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>BW = 2WR < 3RB</math>, there are <math>W+1</math> strategies. |
Latest revision as of 20:24, 28 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 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, .
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.