跳到主要内容
← 返回题库
免费概率中等

Cards Until Two Colours Remain

考察公司Susquehanna International GroupJane Street

题目

A deck has 3535 green, 2525 blue and 4040 red cards, shuffled uniformly at random. You draw cards one at a time without replacement, and stop as soon as one colour has run out, so that only two colours are left in the deck.

(a) What is the expected number of cards left in the deck?

(b) What is the expected number of cards drawn?

解析

先自己试一试，卡住了再打开提示。

提示 1

Don't try to find when you stop. Instead, for one card, ask: what has to happen for it to still be in the deck at the end? Then add up over all cards.

提示 2

A green card is still in the deck exactly when all the blue cards, or all the red cards, were drawn before it. Look at that green card together with the 2525 blue cards: in a random shuffle it is equally likely to be anywhere among these 2626 cards. What is the chance it comes last?

查看解析

Step 1: When is a card still in the deck? You stop right after the last card of some colour is drawn. So a card is still in the deck exactly when some other colour was completely drawn before it. (Its own colour can't be the one that ran out, since the card itself is still there.)

So by linearity of expectation,

E[cards left]=∑cardsP(a whole other colour comes before this card).E[\text{cards left}] = \sum_{\text{cards}} P(\text{a whole other colour comes before this card}).

Step 2: One green card. Two things can put a green card after a whole colour:

  • All 25 blue cards come before it. Look only at this green card and the 2525 blue cards. In a random shuffle, the green card is equally likely to be in any of the 2626 places among them, so it is last with probability 126\tfrac{1}{26}.
  • All 40 red cards come before it: probability 141\tfrac{1}{41}, by the same argument.
  • Both happen, all 6565 blue and red cards before it: probability 166\tfrac{1}{66}.

By inclusion–exclusion,

P(a green card is left)=126+141−166≈0.04770.P(\text{a green card is left}) = \frac{1}{26} + \frac{1}{41} - \frac{1}{66} \approx 0.04770.

Step 3: Blue and red cards, the same way.

P(a blue card is left)=136+141−176≈0.03901,P(\text{a blue card is left}) = \frac{1}{36} + \frac{1}{41} - \frac{1}{76} \approx 0.03901,
P(a red card is left)=136+126−161≈0.04985.P(\text{a red card is left}) = \frac{1}{36} + \frac{1}{26} - \frac{1}{61} \approx 0.04985.

Step 4: Add up over all 100100 cards.

E[cards left]≈35(0.04770)+25(0.03901)+40(0.04985)≈1.66951+0.97525+1.99383≈4.63860.E[\text{cards left}] \approx 35(0.04770) + 25(0.03901) + 40(0.04985) \approx 1.66951 + 0.97525 + 1.99383 \approx 4.63860.

Answers:

(a) E[cards left]≈4.63860E[\text{cards left}] \approx 4.63860.

(b) Every card is either drawn or left, so E[cards drawn]=100−4.63860≈95.36140E[\text{cards drawn}] = 100 - 4.63860 \approx 95.36140.

In general, with gg, bb and rr cards of the three colours,

E[cards left]=g(1b+1+1r+1−1b+r+1)+b(1g+1+1r+1−1g+r+1)+r(1g+1+1b+1−1g+b+1).E[\text{cards left}] = g\Big(\tfrac{1}{b+1} + \tfrac{1}{r+1} - \tfrac{1}{b+r+1}\Big) + b\Big(\tfrac{1}{g+1} + \tfrac{1}{r+1} - \tfrac{1}{g+r+1}\Big) + r\Big(\tfrac{1}{g+1} + \tfrac{1}{b+1} - \tfrac{1}{g+b+1}\Big).

Why so few cards are left: each colour's last card is usually near the bottom of the deck, so even the first colour to run out does so late.