USAMO 2000 Problem 3

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

USAMO 2000 Problem 3

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MithsApprentice

2390 posts

MithsApprentice

#1 h Oct 1, 2005, 12:26 AM • 3 Y

Y by samrocksnature, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MithsApprentice

2390 posts

MithsApprentice

#2 h Oct 1, 2005, 12:26 AM • 3 Y

Y by samrocksnature, Adventure10, Mango247

When replying to the problem, I ask that you make posts for solutions and submit comments, jokes, smilies, etc. separately. Furthermore, please do not "hide" any portion of the solution. Please use LaTeX for posting solutions. Thanks.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

947 posts

#3 h Apr 3, 2007, 5:12 PM • 16 Y

Y by henrypickle, explogabloger, pickten, ilovemath121, Dynamite127, Akababa, utkarshgupta, jam10307, vsathiam, Delray, v_Enhance, e_plus_pi, MathbugAOPS, lneis1, samrocksnature, Adventure10

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(R,W,B)$ 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,B-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 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, $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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

5001 posts

#4 h Apr 19, 2021, 1:56 PM • 2 Y

Y by samrocksnature, centslordm

Unexpectedly nice. Here is a nice "local"-type solution.
The answer is $\min(BW,2WR,3RB)$ . We can achieve $BW$ by removing $B$ blue cards (with $W$ penalty each), then removing the red cards with $0$ penalty each and then the white cards with $0$ penalty each. We can also achieve $2WR$ and $3RB$ with a similar procedure.
Consider the order in which cards are played. If a player first plays three red cards, then one white, then one red, then two blue, we can represent the order as $RRRWRB$ . Define a "C-block" of plays as some consecutive (possibly zero-length) plays in which the same card C is played, so an R-block is red cards for example. Clearly, we can represent every card order as a list of blocks such that every red block is followed by a blue block, every blue block is followed by a white block, and every white block is followed by a red block (except for the last block) and no two consecutive blocks are zero-length. For instance, we can represent $RRRRRBBW$ as a 5-long R-block, a 2-long B-block, and then a 1-long W-block. We can represent $WBBR$ as a 1-long W-block, a 0-long R-block, a 2-long B-block, a 0-long W-block, and finally a 1-long R-block.
Consider some arbitrary play order $P$ . I claim that we can find some play order $P'$ which results in at most as much penalty as $P$ and has fewer nonempty blocks than $P$ , unless $P$ has at most 3 nonempty blocks. If $P$ has more than 4 nonempty blocks, it is clear that at least one of the block orders R-B-W-R, B-W-R-B, W-R-B-W occurs, where the first and fourth blocks are nonempty, while the second and third are not necessarily nonempty.
Focus on the R-B-W-R case. Suppose there are $b$ blue cards in the blue block, $w$ in the white block, $r_1$ in the first red block, and $r_2$ in the second red block. Now consider the following subcases:
Subcase 1: $3b \leq 2w$ . Consider the play order $P'$ formed by deleting the second red block and adding $r_2$ red cards to the first block. For example, if the blocks are $\boxed{RRRR}\boxed{B}\boxed{WW}\boxed{RR}$ before, then they will be $\boxed{RRRRRR}\boxed{B}\boxed{WW}$ . Clearly this decreases the number of nonempty blocks. It is clear that this process increases the penalty by $3r_2b$ , but also decreases it by $2r_2w$ . Since $3b \leq 2w$ , it follows that $2r_2w \geq 3r_2b$ and the penalty does not increase.
Subcase 2: $3b > 2w$ . Consider the play order $P'$ formed by deleting the first red block and adding $r_1$ red cards to the second block. Clearly this decreases the number of nonempty blocks. It is clear that this process increases the penalty by $2r_1w$ , and decreases it by $3r_1b$ . Since $3b>2w$ , it follows that $3r_1b>2r_1w$ and the penalty decreases.
Combining these cases implies that there always exists such a $P'$ for the R-B-W-R case. The other two cases can be dealt with similarly, which implies the claim.

Repeating this process shows that any play order $P$ accumulates at least as much penalty as some play order with three or fewer nonempty blocks. Hence to find the minimum it suffices to only consider play orders with three or fewer nonempty blocks. Clearly if there are at most two nonzero numbers in the multiset $\{R,B,W\}$ , the minimum is zero, which fits the expression. Otherwise, if all of $\{R,B,W\}$ are nonzero, we can easily derive the above expression by considering cases on the order in which blocks are removed, which completes the proof. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

396 posts

#5 h May 16, 2021, 4:47 AM

Y by

JSteinhardt wrote:

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(R,W,B)$ 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,B-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 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, $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.

You are using Induction of which quantity?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1696 posts

awesomeming327.

#6 h Dec 24, 2022, 3:15 AM

Y by

1. Setup
For each order of playing, we write it out by repeatedly appending either $r$ , $w$ , or $b$ based on the color played in that move to the end of a sequence which starts off as empty. For example, if the player plays five reds and then three blues, then we say this player played sequence $\alpha=rrrrrbbb.$ We call a sequence $u$ a subsequence of another one $v$ if and only if we can remove some elements of $v$ and get $u$ . Denote by $\#$ to be a function taking in a sequence and outputting a nonnegative integer that finds the number of times the sequence is a subsequence of $\alpha.$ Note that the penalty is equal to $\#(bw)+2\#(wr)+3\#(rb).$ Call a subsequence of consecutive elements of the same color a block. Furthermore, let a block of $k$ $r$ 's be denoted by $r^k$ .

2. In the minimum-penalty played sequence $\alpha$ , $b$ must be followed by $r$ , $r$ by $w$ , and $w$ by $b$ .
Assume otherwise that we have a played sequence $\alpha$ for which two consecutive elements are $rb$ , $bw$ , or $wr$ . Clearly, transposing these two will not cause change in the penalty induced by any other element. The penalty induced by the second transposed element ( $b$ , $w$ , $r$ , respectively) will also not change. However, the first transposed element's penalty will decrease because we are losing either an $(rb)$ subsequence, a $(bw)$ subsequence, or a $(wr)$ subsequence.

3. If $\alpha$ contains exactly four consecutive blocks, we can decrease that number to three blocks while not increasing the penalty.
Suppose we have $\alpha=w^{a_1}b^{a_2}r^{a_3}w^{a_4}$ . The penalty is $a_2a_4+2a_1a_3.$ Then, $w^{a_1+a_4}b^{a_2}r^{a_3}$ has penalty $2a_1a_3+2a_3a_4$ and $b^{a_2}r^{a_3}w^{a_1+a_4}$ has penalty $a_2a_1+a_2a_4.$ Depending on the relative sizes of $a_2$ and $2a_3$ , one of these must not increase the penalty. The process for the other three cases are similar and I will not go into detail.

4. One minimal-penalty $\alpha$ is in the form $w^{W}b^{B}r^{R}$ or any cyclic shifts.
Note that in $\alpha$ we can apply the previous step to any four consecutive blocks, and we will only affect the penalties of elements inside of that block, and the other blocks will not be affected. Therefore, if we continually apply the algorithm in the previous step, the number of blocks decreases while the penalty doesn't increase. Therefore, one of the minima must be the case where there are three consecutive blocks, in the form $w^{W}b^{B}r^{R}$ or any cyclic shifts. The penalty here is either $BW,2WR,3RB$ so the minimum is $\min(BW,2WR,3RB).$

5. The equality case.
In the final application of the algorithm, as described in step $4$ , the equality case of step $3$ is either $W=3R$ , $B=2R$ , or $2W=3B$ . Therefore, if none of these equalities are true, then the inequality in the final application in step $4$ is strict and so the only minimum case is the one with exactly three blocks. Note that in this case, $BW,2WR,3RB$ are pairwise distinct. If the minimum is $BW$ , then the only minimum case is $b^Br^Rw^W.$ Similar goes for the other cases. The other cases can all be deduced by reverse application of the algorithm in step $4$ mindful of the equality case.

Equal case
@above

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3301 posts

#7 h Jan 4, 2023, 12:30 AM • 2 Y

Y by Jndd, winniep008hfi

The answer is $\boxed{\min(BW, 2RW, 3BR)}$ . Each of these is achievable with $\textbf{BRW}$ , $\textbf{WBR}$ , and $\textbf{RWB}$ , respectively, where $\textbf{B}, \textbf{R}, \textbf{W}$ are some number of (in this case, all) blue cards, red cards, and white cards. We will prove this is minimal.

Consider a moveset that gives minimal penalty (we can assume this since there are finitely many possible movesets), which we will call a $\textit{Mondrian}$ . For convenience, we will let $B$ , $W$ , and $R$ denote a blue, white, and red card when describing a moveset. Then notice that if there exists $BW$ in the moveset, we can switch both to strictly decrease the penalty, which would be a contradiction, so there do not exist $BW$ in any $\textit{Mondrian}$ . Similarly, neither does $WR$ nor $RB$ . Therefore, every $\textit{Mondrian}$ is of the form $X_1X_2X_3\dots X_n$ , where each $X_i$ consists of $R\cdots RW\cdots WB\cdots B$ (where there are a positive number of each $R$ , $W$ , and $B$ ), and $X_1$ may start with $R$ , $W$ , or $B$ and $X_n$ may end with $R$ , $W$ , or $B$ .

When $BW \neq 2RW \neq 3BR \neq BW$ , notice that we can now move the first "block" of cards of the same color in the first $X_i$ to the "block" in the last $X_n$ (with the same color, so red goes into a red block) to strictly decrease the penalty of a $\textit{Mondrian}$ , a contradiction. (If this does not decrease it, do the opposite and move the last block to the first one, since either one is guaranteed to work). Therefore, the $\textit{Mondrian}$ must be of the form we mentioned at the start. There is obviously only $\boxed{1}$ way to achieve this.

By extremely similar logic, we can conclude that
$BW = 2RW \neq 3BR \implies \boxed{W+1}$ ,
$BW = 3BR \neq 2RW \implies \boxed{B+1}$ ,
$2RW = 3BR \neq BW \implies \boxed{R+1}$ , and
$BW = 2RW = 3BR \implies \boxed{R+W+B}$ , done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1292 posts

#8 h Sep 7, 2023, 10:37 PM

Y by

Alright here we go... this sols different from above sols i think and it is legitimately solved
We use a local technique (even though this is in DCY-process :rotfl:

:rotfl:

)

The answer is min(BW,2RW,3RB), obtained by taking all of B then R then W (cyclically shifting for other minimums). Note that WB,RW,BR are more efficient versions of BW,WR,RB, hence we know the dealing of cards occurs in blocks $B_1B_2...B_n$ , where each $B_k$ is a sequence of $R...RW...WB...B$ , and henceforth suppose that we have obtained the minimal penalty config s.t. $n\ge 2$ , with $BW\ne 2RW\ne 3RB$ . Between any $B_k,B_{k+1}$ , having $p,q,r$ and $u,v,w$ number of R,W,B in the respective blocks, we assume the penalty is already optimal, and perturb the penalty by combining only the Rs with each other into the same block $B_k$ , and see if it's more efficient; it increases by 3(ur-qu). If this is not equal to 0, then either putting R in both blocks into $B_k$ or $B_{k+1}$ suffices, since they are negation of each other, so we would combine the blocks s.t. it increases by negative amount, contradiction; if they are 0, q=r; by similar reasoning on other ones, we deduce they are all =0, meaning combining blocks with their respective color doesn't change the optimality.

We're now home free: ,We can WLOG combine them, and now apply this algorithm GLOBALLY to show that (at least one of the) minimum(s) is when it's one block of R...RW...WB...B.
It remains to find the number of ways: There's one way if $BW\ne 2RW\ne 3RB\ne BW$ , which is playing all of one type at once; if $BW=2RW\ne 3RB$ there's W+1 ways (erasing 0 to W of white cards, then playing out all blue cards, then all red cards, and finish with the rest of white cards. (Each white card discarded still preserves $BW = 2WR$ .)

For the second part, the motivation was that the R and B must now be in one block due to our above reasoning, but we can have white separated, because it holds the same equality as if it were R...RW...WB...B, but it wouldn't hold the equality as the same if we had done R...RW...WB...B with a blue not in the block of blues (easily checked, remember that we can WLOG combine the other blocks). We can apply similar reasoning in other cases to get 1,W+1,B+1,R+1,R+W+B ways in their respective equals.

This post has been edited 2 times. Last edited by huashiliao2020, Sep 7, 2023, 10:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

738 posts

#9 h Nov 19, 2024, 5:16 PM

Y by

Guess who else localed a DCY-process

Attachments:

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

100 posts

#10 h Apr 4, 2025, 9:08 PM

Y by

What does DCY means?

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a