Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1975 USAMO Problems/Problem 5"
m (→‎Solution 3)
 
(8 intermediate revisions by 4 users not shown)
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==
+
==Solutions==
 
===Solution 1===
 
===Solution 1===
  
Line 12: Line 12:
  
 
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.
 
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.
 +
 +
Also, note that when second ace is still the second ace when we draw the deck backwards. (we need to note this, else this argument holds for the first ace and third ace as well)
  
 
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.
 
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==
+
 
 +
===Solution 3===
 +
 
 +
Like Solution 2, this solution is also a direct solution.
 +
 
 +
The three aces divide the deck into four piles with a non-negative number of cards. Let <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> be the number of cards in the first, second, third, and fourth piles, respectively, given a random deck <math>D</math>. Also, let <math>E(a), E(b), E(c), E(d)</math> denote the expected value of <math>a</math>, <math>b</math>, <math>c</math>, and <math>d</math> over all decks <math>D</math>. Then <math>a + b + c + d = n - 3</math> (the deck minus the three aces).
 +
 
 +
For every deck <math>D</math>, there must exist other decks that permute the values of <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math>. (i.e. if there is a deck with <math>a = 2, b = 3, c = 1, d = 4,</math> there exists a deck with <math>a = 1, b = 2, c = 3, d = 4</math>.) Therefore, the value of <math>a</math> over all decks <math>D</math> is a permutation of the value of <math>b</math> over all such decks, and as a result <math>E(a) = E(b)</math>. A similar result holds for <math>b</math>, <math>c</math>, and <math>d</math>, and so <math>E(a) = E(b) = E(c) = E(d)</math>. Because <cmath>E(a) + E(b) + E(c) + E(d) = E(a + b + c + d) = E(n-3) = n-3,</cmath> <math>E(a) = E(b) = \frac{n-3}{4}</math>. We want to compute the number of cards up to and including the second ace, which is just <cmath>E(a) + 1 + E(b) + 1 = \frac{n-3}{2} + 2 = \frac{n+1}{2},</cmath> as desired.
 +
 
 +
 
 +
{{alternate solutions}}
 +
 
 +
==See Also==
  
 
{{USAMO box|year=1975|num-b=4|after=Last Question}}
 
{{USAMO box|year=1975|num-b=4|after=Last Question}}
 +
{{MAA Notice}}
  
 
[[Category:Olympiad Combinatorics Problems]]
 
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 01:30, 30 December 2017

Problem

A deck of $n$ 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 $(n+1)/2$.

Solutions

Solution 1

We begin by induction. Our base case is naturally when $n = 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 $(3 + 1)/2$. Next, we assume that the expected number of cards required to pull the second ace from a deck of n cards is in fact $(n + 1)/2$. Now, we see that to simulate the case with $n + 1$ cards, we simply must add a card to our deck. By our assumption, we can expect to turn up $(n + 1)/2$ cards to be turned up, including our second ace. Thus ahead of our second ace, we expect $(n - 1)/2$ cards , and after it $(n - 1)/2$ 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 $((n + 1)/2) + 1/2)$, or $(n + 2)/2$, the desired outcome for the $n + 1$ 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 $k$th place. If we draw the deck backwards (which has equal probability as drawing it forwards), then we will draw it in the $n+1-k$th place, since the $n$th place will become the first, the $n-1$th the second, etc.

Also, note that when second ace is still the second ace when we draw the deck backwards. (we need to note this, else this argument holds for the first ace and third ace as well)

Now, this implies that the expected location of the second ace is in the $(k+n+1-k)/2=(n+1)/2$ place.


Solution 3

Like Solution 2, this solution is also a direct solution.

The three aces divide the deck into four piles with a non-negative number of cards. Let $a$, $b$, $c$, and $d$ be the number of cards in the first, second, third, and fourth piles, respectively, given a random deck $D$. Also, let $E(a), E(b), E(c), E(d)$ denote the expected value of $a$, $b$, $c$, and $d$ over all decks $D$. Then $a + b + c + d = n - 3$ (the deck minus the three aces).

For every deck $D$, there must exist other decks that permute the values of $a$, $b$, $c$, $d$. (i.e. if there is a deck with $a = 2, b = 3, c = 1, d = 4,$ there exists a deck with $a = 1, b = 2, c = 3, d = 4$.) Therefore, the value of $a$ over all decks $D$ is a permutation of the value of $b$ over all such decks, and as a result $E(a) = E(b)$. A similar result holds for $b$, $c$, and $d$, and so $E(a) = E(b) = E(c) = E(d)$. Because \[E(a) + E(b) + E(c) + E(d) = E(a + b + c + d) = E(n-3) = n-3,\] $E(a) = E(b) = \frac{n-3}{4}$. We want to compute the number of cards up to and including the second ace, which is just \[E(a) + 1 + E(b) + 1 = \frac{n-3}{2} + 2 = \frac{n+1}{2},\] as desired.


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1975 USAMO (Problems • Resources)
Preceded by
Problem 4 		Followed by
Last Question
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1975_USAMO_Problems/Problem_5&oldid=89273"