Author |
Topic: 2n+1 coins (Read 3109 times) |
|
NickH
Senior Riddler
Gender: 
Posts: 341
|
 |
2n+1 coins
« on: Oct 10th, 2002, 12:39am » |
 Quote  Modify
|
Player A has n+1 coins, while player B has n coins. Both players throw all of their coins simultaneously and observe the number that come up heads. Assuming all the coins are unbiased, what is the probability that A obtains more heads than B?
Nick
|
| « Last Edit: Oct 10th, 2002, 11:00am by NickH » |
 IP Logged |
Nick's Mathematical Puzzles
|
|
|
Garzahd
Guest
|
Well, testing N=1, 2, and 3, it seems to come out to 50% every time.
So let's try induction (haven't thought this through all the way yet...)
Base case: N=1. If B comes up heads, A has a 1/4 chance of beating him with 2 heads; otherwise A has a 3/4 chance. That's pretty clearly 50% overall.
Then, given an N for which the odds are 50%, let's add a coin for each and prove that the odds for N+1 are also 50%.
If the added coins are either both heads or both tails, the relative number of each hasn't changed; odds are still 50%.
Now just to figure out why giving A the extra head, averaged with giving B the extra head, also comes out to 50%.
Which is where I'm stuck at the moment. Anyone want to try a different tack?
|
|
IP Logged |
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: 2n+1 coins
« Reply #2 on: Oct 10th, 2002, 2:47pm » |
Quote Modify
|
Sure, try it like this.
Give B an n+1th coin, only magically make it so the n+1th coin always comes up tails. It's pretty clear that B's set of flips can be put into one-to-one correspondence with A's flips where the last coin comes up tails, leaving half the cases victories for A.
|
|
IP Logged |
My arcade cabinet
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: 2n+1 coins
« Reply #3 on: Oct 11th, 2002, 10:17am » |
Quote Modify
|
You can directly find the probabilities:
A wins if A gets more heads than B.
probability that A wins = summ=0..n( 1/2nchoose(n,k) * sump=m+1..n+1( 1/2n+1choose(n+1,p) ) )
probability that A loses = summ=0..n( 1/2nchoose(n,k) * sump=0..m( 1/2n+1choose(n+1,p) ) )
With a little manipulation, you'll find that these are the same sum.
|
|
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: 2n+1 coins
« Reply #4 on: Oct 11th, 2002, 7:50pm » |
Quote Modify
|
Probability of A>B after A's N+1 flips, p, is
p= P(A>B) + 0.5*P(A=B)
where capital P(E) means probability of event E, after each player has flipped N times. This is because A will either already be ahead after N flips, or has a 50% chance of breaking the tie in the case of A=B after N flips.
Since P(A>B)=P(B>A):
2*p = 2*P(A>B) + P(A=B) = P(A>B) + P(B>A) + P(A=B)
But this equals 1 because it covers all possiblities after N flips, so p=0.5.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove