Difference between revisions of "1975 USAMO Problems/Problem 5"
God of Math (talk | contribs) (→Solution) |
God of Math (talk | contribs) (→Solution) |
||
Line 4: | Line 4: | ||
==Solution== | ==Solution== | ||
− | We begin by induction. Our base case is naturally when <math>n</math> = 3, as there can be no less than 3 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 2 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 n + 1 cards, we simply must add a card to our deck. | + | We begin by induction. Our base case is naturally when <math>n</math> = 3, 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. |
==See also== | ==See also== |
Revision as of 11:53, 4 August 2009
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
We begin by induction. Our base case is naturally when = 3, 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.
See also
1975 USAMO (Problems • Resources) | ||
Preceded by Problem 4 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |