Maths Olympiad Prep

Library / /32 of 115

Combinatorics Difficulty 7.0 National olympiad, round 2 Find the answer

A game of solitaire is played with RR red cards, WW white cards, and BB 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,R, W, and B,B, the minimal total penalty a player can amass and all the ways in which this minimum can be achieved.

A number or a short expression. Spacing and $ signs are ignored.

Solution

We claim (inductively) that the minimum is just going to be min(BW,2WR,3RB)\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)f(B,W,R) be the minimum we seek. Note that f(B,W,R)=min(W+f(B1,W,R),2R+f(B,W1,R),3B+f(B,W,R1))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(B1,W,R)=min((B1)W,2WR,3R(B1))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((B1)W,2WR,3R(B1))<min(BW,2WR,3RB)W+\min((B-1)W,2WR,3R(B-1)) < \min(BW,2WR,3RB) . It is evident that the first two entries in the minmin expression cannot cause this to happen, so that we need only consider W+3R(B1)<min(BW,2WR,3RB)W+3R(B-1) < \min(BW,2WR,3RB) . So W+3R(B1)<BWW+3R(B-1) < BW , whence 3R<W3R < W . But W+3R(B1)<3RBW+3R(B-1) < 3RB , so that W<3RW < 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)f(B,W,R) is indeed min(BW,2WR,3RB)\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 BW2WR3RBBW \neq 2WR \neq 3RB , there is only 11 optimal strategy.
Suppose, now, that BW=2WRBW = 2WR . It is thus optimal to discard either a BB or WW card. If we ever discard a blue card, then we will cause BW<2WRBW < 2WR , whence there is only one possible strategy from then on. However, if we discard a white card, then we will still have BW=2WRBW = 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 WW times, there are W+1W+1 choices for how many WW cards to discard ( 00 to WW ), meaning that there are W+1W+1 optimal strategies.
By similar logic, we get R+1R+1 optimal strategies if 2WR=3RB2WR = 3RB , and B+1B+1 optimal strategies if 3RB=BW3RB = BW .
The final case, then, is if BW=2WR=3RBBW = 2WR = 3RB . In this case, if we first discard a white card, we are left with the BW=2WRBW = 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+RB+W+R .
To summarize:
The minimum penalty is min(BW,2WR,3RB)\min(BW,2WR,3RB) .
If BW2WR3RBBW \neq 2WR \neq 3RB , there is 11 optimal strategy.
If BW=2WR<3RBBW = 2WR < 3RB , there are W+1W+1 strategies.
If 2WR=3RB<BW2WR = 3RB < BW , there are R+1R+1 strategies.
If 3RB=BW<2WR3RB = BW < 2WR , there are B+1B+1 strategies.
If BW=2WR=3RBBW = 2WR = 3RB , there are R+B+WR+B+W strategies.
By J Steinhardt, from AoPS Community

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.