Author |
Topic: Easy: COIN UNBIASING (Read 13329 times) |
|
Ion Rush
Guest
|
You and your arch rival are competing for the same girl. After years of battling, you both decide to settle it by tossing a coin.
Your rival produces a coin, but you don't happen to have one on you. You are certain that the coin your rival has produced is loaded, ie. it will come up with heads more than 50% of the time on average.
How do you arrange a fair contest, based purely on chance and not skill, by flipping this coin?
are these acceptable solutions
each person strives for the longest string of a single occurance
(i.e. heads heads heads heads tials would beat heads heads heads tails)
each person flipps the coin 10 times. The winner is the one who gets the most heads in those 10 tosses. Ties cause a repeat
the 2 guys and one girl flip the coin, The odd person out leaves and the two matching people date.(HHT, T leaves) If all 3 get the same result (likely with a biased coin) it is repeated. If the girl gets the odd result the outcome is ignored.
|
|
 IP Logged |
|
|
|
Adam Hanig
Guest
|
Let us assume that each person has not already chosen a side. This test relies on you, the one who did not bring the coin, calling it in the air.
So have him flip, and you call it. The variability is now on what you call, so assuming you are completely ignorant as to how it is loaded (which your competitor assumes), then it is 1/2 from both perspectives, completely fair.
However, the way the question is worded indicates that you know the coin is loaded for heads. Perhaps thats the only version of loaded coin they sell in town, or you switched it to while he wasn't looking. Then just call heads, and things are in your advantage!
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
Re: Easy: COIN UNBIASING
« Reply #2 on: Jul 27th, 2002, 11:11am » |
 Quote  Modify
|
Another decent solution:
1) Flip the coin twice.
2) If you get HT, guy #1 wins. If you get TH, guy #2 wins. These are equally probably, regardless of p.
3) If you get HH or TT, go to step 1).
|
|
IP Logged |
|
|
|
BigBadBert
Guest
|
|
Re: Easy: COIN UNBIASING
« Reply #3 on: Jul 29th, 2002, 12:27pm » |
Quote Modify
 Remove
|
Place the coin on the ground (or table or back of your hand) where the other person can't see it and ask the other person to call it.
Just another possible way.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Easy: COIN UNBIASING
« Reply #4 on: Jul 29th, 2002, 1:39pm » |
Quote Modify
|
on Jul 27th, 2002, 11:11am, srowen wrote:Another decent solution:
1) Flip the coin twice.
2) If you get HT, guy #1 wins. If you get TH, guy #2 wins. These are equally probably, regardless of p.
3) If you get HH or TT, go to step 1). |
|
Just to add some background, this was one of the classic problems mathematician John Von Neumann was interested in when he was developing game theory. Srowen's solution shown above is originally attributed to Von Neumann.
Here's a short paper on the subject:
http://www.ocf.berkeley.edu/~wwu/riddles/coinflip.pdf
I think BigBadBert's solution is pretty clever BTW 
|
| « Last Edit: Jul 29th, 2002, 1:41pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
continuum
Newbie
 
Gender:
Posts: 14
|
|
Re: Easy: COIN UNBIASING
« Reply #5 on: Aug 25th, 2002, 9:03pm » |
Quote Modify
|
The first solution I thought was the same that srowen said.
But I tried to think in a solution with a limited number of flips, since you could have to wait a long time before it shows something like HT or TH. In fact, with a chance of 100% of H or T, you would wait forever. 
Then and I arrived at the same solution of Adam Hanig, that uses only one flip.
When I read BigBadBert's solution, I thought of another tricky one:
You hide the coin in one of your hands, and ask your rival to guess which hand has it. Okay, this is too much tricky, I know. 
|
|
IP Logged |
|
|
|
rfeague
Newbie
Posts: 5
|
|
Re: Easy: COIN UNBIASING
« Reply #6 on: Sep 7th, 2002, 4:43pm » |
Quote Modify
|
How about this: we know that heads is more likely. So both parties take turns flipping until they get tails. Whoever gets tails in fewer flips wins. If you both get tails on the first try, restart. That seems more efficient than the other approaches.
|
|
IP Logged |
|
|
|
greatly_amuzed
Newbie
Posts: 4
|
|
Re: Easy: COIN UNBIASING
« Reply #7 on: Sep 8th, 2002, 11:25pm » |
Quote Modify
|
A very practical solution: Why can't the girl just choose which bloke she likes better? 
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Easy: COIN UNBIASING
« Reply #8 on: Oct 9th, 2002, 8:53pm » |
Quote Modify
|
Anyone have a solution to the variation (using a fair coin to produce a result with probability = P>.5). I know a solution, but will not pretend it is my own: I read it (perhaps from the same source as the esteemed Mr. Wu  ). I'm curious to see if someone has a different idea!
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Easy: COIN UNBIASING
« Reply #9 on: Oct 11th, 2002, 12:58am » |
Quote Modify
|
Icarus, you may need to explain that variation more clearly. What you seem to be saying is too trivial, so I'm assuming you meant something different. I.e., flip the fair coin twice, and say that you win if the flips were not both tails. Then p=0.75. You can obtain (or at least approximate as closely as you like) any probability with a sufficient number of flips.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Easy: COIN UNBIASING
« Reply #10 on: Oct 11th, 2002, 3:16pm » |
Quote Modify
|
What I mean is the variation that William Wu gives with the problem:
Quote:Variation: (COIN BIASING) You and your rival are competing for the same girl, and decide to settle it with a coin toss. Your rival has known the girl longer than you have, so you agree that it is fair for him to have a chance of winning equal to P, where P > 0.5. However, you only have a fair coin. How can you conduct this contest such that the biased probability is manifested? What is the average number of coin flips needed to determine a winner?
|
|
The solution I refered to is exact, regardless of the value of P, though for some values of P, you could theoretically go on forever without deciding the question. ( The probability of this is zero, but that is not the same thing as saying it cannot happen.) I am curious if someone can find a different exact solution.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: Easy: COIN UNBIASING
« Reply #11 on: Oct 11th, 2002, 5:01pm » |
Quote Modify
|
I have a solution to that as well, but I've known it for awhile so I don't remember if I came up with it myself or read it somewhere Probably the same as yours, Icarus.
|
|
IP Logged |
My arcade cabinet
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: Easy: COIN UNBIASING
« Reply #12 on: Oct 11th, 2002, 7:11pm » |
Quote Modify
|
I just saw this, and thought it was very interesting! I had an idea, but I'm in a bit of a hurry, so excuse me if the following is all nonsense.
Suppose you want to answer YES to a question with probability P.
Given a number P such that 0 <= P <= 1, if you randomly choose a number x on the interval [0,1], there is a probability P that x will be less than P.
All right. Now consider the binary expansion of P, which will be 0.b1b2... . There may be only zeroes after some point. Start flipping the fair coin, and interpret the n-th result as the n-th binary place (this sounds funny ) of a real number r between 0 and 1. If some digit of r ever differs from the corresponding digit in P, stop.
If the number r you obtained in this manner is less than P, answer YES. Otherwise, answer NO. It seems pretty clear to me that this achieves the desired result (with probability 0 that it goes on forever), but I also have a feeling this is the answer everyone already knows. 
I also don't see the reason for the restriction p > 0.5... be patient, I'm REALLY in a hurry.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: Easy: COIN UNBIASING
« Reply #13 on: Oct 11th, 2002, 9:52pm » |
Quote Modify
|
Hi, Pietro. I'm sure that's correct, and it's probably what everyone had in mind. It's also what I had in mind when I said you could approximate the probability as closely as you like -- I was assuming a fixed bound on the number of flips, but if you let the number of flips be unbounded, you get an exact result.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Easy: COIN UNBIASING
« Reply #14 on: Oct 12th, 2002, 9:13am » |
Quote Modify
|
Yes, that was the solution I was refering to. I read it in a book by Martin Gardner (a collection of some of his Scientific American columns) many years ago! Say, William, how about you take over for Martin! After he retired, Sci-Am's replacements have never been as good.  The last I saw (I canceled my subscription after they decided to become a clone of "Discover") was a mere puzzle column, with little challenge, and no discussion. One thing I really like about this site is your appreciation that the true worth of a puzzle is not in simply finding a solution, but in the thought processes that lead to the solution, and in what new thoughts that solution can evoke!
There is no reason for the restriction P > .5. I assume that it is in there simply because the narration led to it.
Also, unless I've made an error , the average number of flips needed to decide the matter is 2.
|
| « Last Edit: Oct 12th, 2002, 9:31am by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Easy: COIN UNBIASING
« Reply #15 on: Jan 22nd, 2003, 1:29pm » |
Quote Modify
|
on Aug 25th, 2002, 9:03pm, continuum wrote:When I read BigBadBert's solution, I thought of another tricky one:
You hide the coin in one of your hands, and ask your rival to guess which hand has it. Okay, this is too much tricky, I know. |
|
Actually, I dunno what we were smoking on this one. The human mind is a poor random number generator. Your rival might be inclined to choose the right hand based on what he heard on the radio that morning or some other nonsense. It's like on that Regis show where they ask people to choose random numbers so an audience member can win something -- I'm sure some numbers get chosen much more often than others.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Easy: COIN UNBIASING
« Reply #16 on: Mar 17th, 2003, 7:41am » |
Quote Modify
|
A colleague of mine recently suggested the following solution: just spin the coin. When the coin comes to rest, it's equally likely that the side facing up will be heads or tails. Do you think that's reasonable? On one hand, everyone probably spins coins with roughly the same force. On the other, the micro perturbations between the tabletop surface and the coin might be significant enough and random enough to make the outcome equiprobable.
On another note, if the heads side of a coin was heavier than the tails side, would that make the heads side more likely to face the floor after a flip? My intuition says no but I'm not confident. If the answer is no, how would you physically construct a biased coin?
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Easy: COIN UNBIASING
« Reply #17 on: Mar 17th, 2003, 4:36pm » |
Quote Modify
|
I don't know - My intuition tells me that the heavier side is more likely to come out on the bottom of a spun coin (assuming that the portion of the edge that is contacting the surface on which it is spinning is level and smooth). If one side of the coin is heavier than the other, then the coin's CG is going to be closer to that side. That means that the small perturbations of the coin's angle that eventually cause it to precess and fall over are more likely to reach the "point of no return" on that side than on the other.
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Easy: COIN UNBIASING
« Reply #18 on: Mar 17th, 2003, 11:13pm » |
Quote Modify
|
it all depends on how you spin the coin.. I can bias it pretty well in my favour..
I can even do it with a die sometime (in the end it's pretty much deterministic classical mechanics, just a matter of throwing right)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Easy: COIN UNBIASING
« Reply #19 on: Mar 20th, 2003, 7:42pm » |
Quote Modify
|
Even ordinary coins which are "fair" (or as close an approximation as anybody could need) when flipped can be horribly biased when spun. I think this is because of irregularities on the edge of the coin: A slight taper, for instance, could cause this bias. I once had a silver dollar which had about an 80-20 bias in favor of tails, when spun. On the other hand, if neither you nor your rival know in which direction the coin is spin-biased, then it's fair for much the same reason that "Call it in the air" is.
|
|
IP Logged |
|
|
|
ozzz169
Newbie
Posts: 5
|
|
Re: Easy: COIN UNBIASING
« Reply #20 on: Feb 10th, 2009, 1:43pm » |
Quote Modify
|
I know this is old but I am new so here is my 2 cents:
fav answer to get the fair one...
just guy that calls it cant be the guy who brought the coin as he has 50% chance of calling what it will land on regaurdless of how its biased... could land on heads 100% but he does not know that so he has 50% chance to call heads... and therfor 50% chance to win.
for the unbias to creat bias....
I am sure there is more elegent way to the second question... but I would just give the odds..... for example if p=.6 then he should have 60 percent and other guy 40 then he has to get to 4 wins before you get to 6 wins...... lets just hope p=a rational number or this would not work as they would take forever.. if p= .6534214564 then i got to get to that before he gets to 1-p and that will take a while
in other words I have to get p wins and he has to get to 1-p wins... you can also reduce when possible. ex above he could get to 2 wins before I get to 3 is still valid.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Easy: COIN UNBIASING
« Reply #21 on: Feb 12th, 2009, 9:09am » |
Quote Modify
|
on Mar 17th, 2003, 7:41am, william wu wrote:| A colleague of mine recently suggested the following solution: just spin the coin. When the coin comes to rest, it's equally likely that the side facing up will be heads or tails. Do you think that's reasonable? On one hand, everyone probably spins coins with roughly the same force. On the other, the micro perturbations between the tabletop surface and the coin might be significant enough and random enough to make the outcome equiprobable. |
|
Actually, coins are not disks but cylinders. They have 2 edges. When they spin they spin on only one edge. And on a flat surface the edge doesnt' tend to change. If you start spinning the coin with one side facing up slightly, that side is likely to end up.
|
|
IP Logged |
|
|
|
nakli
Junior Member
Gender:
Posts: 62
|
|
Re: Easy: COIN UNBIASING
« Reply #22 on: Sep 29th, 2009, 4:01am » |
Quote Modify
|
This wasn't as easy as it looked!
My solution to the first part is : The girl tosses the coin. The first person makes a call (heads or tails,doesn't matter!). Now only the girl and first person see the outcome. It is simply win(i.e, he got what he called) or loose. Now the second person has to choose whether he wants this outcome for himself or the first person.
My solution to the second part : Consider probability of first person required is p/q. Now we do something like in the famous "the three doors" probability problem.
Step1: The second person tosses the coin 'mq' times and note the number of heads and tails that occur. He gives this list of outcomes to the girl in an envelope, which the girl is not allowed to open right now.
Step2: The second person asks the first person to tell the number of total heads(or tails,whatever. Its the choice of the second person) that occurred.
Step3: The first person may now chooses 'mp' numbers from "1..mq" (all are equally likely to occur).
Step4: Now, as in the "three doors problem" the second person reveals to him k number of incorrect options. The girl now chooses for the first person whether he should flip the choice or stay with it.
Now if he stays with it the probability of him winning is obviously mp/mq=p/q. If he flips the probability of him winning would be ((mq-1)/mq)*1/(mq-k-1). Lets call this A. values of m and k may be so chosen according to given p such that A=p/q.
|
|
IP Logged |
I was born naked on a bed with a lady.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7526
|
|
Re: Easy: COIN UNBIASING
« Reply #23 on: Sep 29th, 2009, 6:58am » |
Quote Modify
|
on Jul 27th, 2002, 3:50am, Ion Rush wrote:| If the girl gets the odd result the outcome is ignored. |
|
Why  .
|
|
IP Logged |
|
|
|
nakli
Junior Member
Gender:
Posts: 62
|
|
Re: Easy: COIN UNBIASING
« Reply #24 on: Oct 1st, 2009, 3:27am » |
Quote Modify
|
i think i have made some calculation errors...
Any ways I hope my idea is clear...
|
|
IP Logged |
I was born naked on a bed with a lady.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print