2000 USAMO Problems/Problem 3
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.
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
|2000 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|