Competition problem — Combinatorics

Library / /80 of 82

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

In preparation for a game of Fish, Carl must deal 48 cards to 6 players. For each card that he deals, he runs through the entirety of the following process:
1. He gives a card to a random player.
2. A player $Z$ is randomly chosen from the set of players who have at least as many cards as every other player (i.e. $Z$ has the most cards or is tied for having the most cards).
3. A player $D$ is randomly chosen from the set of players other than $Z$ who have at most as many cards as every other player (i.e. $D$ has the fewest cards or is tied for having the fewest cards).
4. $Z$ gives one card to $D$ .
He repeats steps 1-4 for each card dealt, including the last card. After all the cards have been dealt, what is the probability that each player has exactly 8 cards?

Solution

Solution:

After any number of cards are dealt, we see that the difference between the number of cards that any two players hold is at most one. Thus, after the first 47 cards have been dealt, there is only one possible distribution: there must be 5 players with 8 cards and 1 player with 7 cards. We have two cases:

- Carl gives the last card to the player with 7 cards. Then, this player must give a card to another, leading to an uneven distribution of cards.

- Carl gives the last card to a player already with 8 cards. Then, that player must give a card to another; however, our criteria specify that he can only give it to the player with 7 cards, leading to an even distribution.

The probability of the second case happening, as Carl deals at random, is $\frac{5}{6}$ .

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.