Difference between revisions of "1975 USAMO Problems/Problem 5"
God of Math (talk | contribs) (→Solution) |
(Yay nice solution I came up with) |
||
Line 2: | Line 2: | ||
A deck of <math>n</math> playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is <math>(n+1)/2</math>. | A deck of <math>n</math> playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is <math>(n+1)/2</math>. | ||
− | ==Solution== | + | ==Solution 1== |
We begin by induction. Our base case is naturally when <math>n = 3</math>, as there can be no less than <math>3</math> cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires <math>2</math> moves. This indeed is equal to <math>(3 + 1)/2</math>. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact <math>(n + 1)/2</math>. Now, we see that to simulate the case with <math>n + 1</math> cards, we simply must add a card to our deck. By our assumption, we can expect to turn up <math>(n + 1)/2</math> cards to be turned up, including our second ace. Thus ahead of our second ace, we expect <math>(n - 1)/2</math> cards , and after it <math>(n - 1)/2</math> as well. When we add our card, it is ahead of the second ace half the time, and behind if half the time. Therefore we expect to add one card to the number of cards drawn half the time, and add nothing for half the time. Hence we expect to add half a card, and the expected value is now <math>((n + 1)/2) + 1/2)</math>, or <math>(n + 2)/2</math>, the desired outcome for the <math>n + 1</math> case. | We begin by induction. Our base case is naturally when <math>n = 3</math>, as there can be no less than <math>3</math> cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires <math>2</math> moves. This indeed is equal to <math>(3 + 1)/2</math>. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact <math>(n + 1)/2</math>. Now, we see that to simulate the case with <math>n + 1</math> cards, we simply must add a card to our deck. By our assumption, we can expect to turn up <math>(n + 1)/2</math> cards to be turned up, including our second ace. Thus ahead of our second ace, we expect <math>(n - 1)/2</math> cards , and after it <math>(n - 1)/2</math> as well. When we add our card, it is ahead of the second ace half the time, and behind if half the time. Therefore we expect to add one card to the number of cards drawn half the time, and add nothing for half the time. Hence we expect to add half a card, and the expected value is now <math>((n + 1)/2) + 1/2)</math>, or <math>(n + 2)/2</math>, the desired outcome for the <math>n + 1</math> case. | ||
+ | |||
+ | ==Solution 2== | ||
+ | |||
+ | Although we can induct as in the situation above, we can use a more direct approach. | ||
+ | |||
+ | Consider a deck. The second ace is in the <math>k</math>th place. If we draw the deck backwards (which has equal probability as drawing it forwards), then we will draw it in the <math>n+1-k</math>th place, since the <math>n</math>th place will become the first, the <math>n-1</math>th the second, etc. | ||
+ | |||
+ | Now, this implies that the expected location of the second ace is in the <math>(k+n+1-k)/2=(n+1)/2</math> place. | ||
==See also== | ==See also== |
Revision as of 14:13, 13 May 2011
Contents
Problem
A deck of playing cards, which contains three aces, is shuffled at random (it is assumed that all possible card distributions are equally likely). The cards are then turned up one by one from the top until the second ace appears. Prove that the expected (average) number of cards to be turned up is .
Solution 1
We begin by induction. Our base case is naturally when , as there can be no less than cards in the deck. The only way to turn up the second ace is to turn up the first, and then turn up the second, which requires moves. This indeed is equal to . Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact . Now, we see that to simulate the case with cards, we simply must add a card to our deck. By our assumption, we can expect to turn up cards to be turned up, including our second ace. Thus ahead of our second ace, we expect cards , and after it as well. When we add our card, it is ahead of the second ace half the time, and behind if half the time. Therefore we expect to add one card to the number of cards drawn half the time, and add nothing for half the time. Hence we expect to add half a card, and the expected value is now , or , the desired outcome for the case.
Solution 2
Although we can induct as in the situation above, we can use a more direct approach.
Consider a deck. The second ace is in the th place. If we draw the deck backwards (which has equal probability as drawing it forwards), then we will draw it in the th place, since the th place will become the first, the th the second, etc.
Now, this implies that the expected location of the second ace is in the place.
See also
1975 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |