Maths Olympiad Prep

Library / /75 of 82

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Toward the end of a game of Fish, the 22 through 77 of spades, inclusive, remain in the hands of three distinguishable players: DBR\mathrm{DBR}, RB\mathrm{RB}, and DBDB, such that each player has at least one card. If it is known that DBRDBR either has more than one card or has an even-numbered spade, or both, in how many ways can the players' hands be distributed?

Solution

Solution:

Answer: 450450

First, we count the number of distributions where each player has at least 11 card. The possible distributions are:

- Case 1: 4/1/14 / 1 / 1 : There are 33 choices for who gets 44 cards, 66 choices for the card that one of the single-card players holds, and 55 choices for the card the other single-card player holds, or 3×6×5=903 \times 6 \times 5 = 90 choices.

- Case 2: 3/2/13 / 2 / 1 : There are 66 choices for the single card, (52)=10\binom{5}{2} = 10 choices for the pair of cards, and 3!=63! = 6 choices for which player gets how many cards, for a total of 6×10×6=3606 \times 10 \times 6 = 360 choices.

- Case 3: 2/2/22 / 2 / 2 : There are (62)=15\binom{6}{2} = 15 choices for the cards DBRDBR gets, (42)=6\binom{4}{2} = 6 for the cards that RBRB gets, and DBDB gets the remaining two cards. This gives a total of 15×6=9015 \times 6 = 90 choices.

Thus, we have a total of 90+360+90=54090 + 360 + 90 = 540 ways for the cards to be distributed so that each person holds at least one.

Next, we look at the number of ways that the condition cannot be satisfied if each player has at least one card. Then, DBRDBR must have no more than one card, and cannot have an even spade. We only care about cases where he has a non-zero number of cards, so he must have exactly 11 odd spade. Then, we see that there are 252=302^{5} - 2 = 30 ways to distribute the other 55 cards among RBRB and DBDB so that neither has 00 cards. Since there are 33 odd spades, this gives 3×303 \times 30 bad cases, so we have 54090=450540 - 90 = 450 ones where all the problem conditions hold.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.