Heads, or Tails?

Article
08/12/2005

Here's a nifty little problem that a friend gave me yesterday that i thought i'd share with you:

You have three items (call them 'a', 'b' and 'c') that you want to choose any one from without bias. If you had a fair three sided die, you could assign an item to each side of the die, then simply toss the die once and pick the item that it lands on.

However, you don't have such a fair three sided die. Instead, you have a fair two sided coin. Note: 'fair' means 'there is an equal chance of coming up heads or tails'. Can you come up with an algorithm that uses said coin in order to pick any one of those items with equal probability?

Have fun!

---

Edit: Clarified the wording for how 'fair' is defined. Sorry if this tripped anyone up.

Comments

Anonymous
August 11, 2005

Throw the coin twice.
2. if throws were "h-h" select 'A'
if throws were "h-t" select 'B'
if throws were "t-h" select 'C'
if throws were "t-t" goto(1)

So it's not finite. so what? We've got time.

Anonymous
August 11, 2005
Ariel: I asked for an algorith: http://en.wikipedia.org/wiki/Algorithm

i.e. "a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state"

"So it's not finite. so what? We've got time."

Well, considering i asked for something that terminates, it matters :)
Anonymous
August 11, 2005
It's very easy to come up with an algorithm as follows.

The algorithm has a decision cycle (described below) with the following possible results
1. No decision. Probability 0.25
2. Clear winner. Probability 0.375
3. Clear loser. Probability 0.375.

If the result of the decision cycle is 'No decision' repeat the cycle until a different result is obtained. the probability of two 'No decisions' in a row is 0.0625, of three is 0.015625 and of 4 is 0.00390625. The chance of an infinite number is zero, or impossible.

When an different answer is obtained there is either a clear winner, or a clear loser. If there is a clear winner the choice has been made. If there is a clear loser then the decision is made between the other two items on the basis of a single toss of the coin.

The decision cycle:
1. Assign the score 1 to one side of the coin and zero to the other side.
2. Toss the coin once for each item giving a score for that item.
3. Possible outcomes:-
a. Clear winner: Only 1 item with score of 1.
b. Clear losser: Only 1 item with score of 0.
c. No decision: Some other result.

The down side of my solution is that it could potentially take too long.
Anonymous
August 11, 2005
Using a two sided coin means that the set of outcomes will always be a power of two. I don't think any powers of two are divisible by three.

Is there a solution? This one will bug me!
Anonymous
August 11, 2005
After further thought I actually believe that an answer that is required to finish within a given number of throws of the coin is impossible. ie within a given finite time.

If you throw the coin N times you have 2 to the power N equally possible outcomes. To fairly decide between 3 possabilities this number would need to be divisible by three. However the only factors of this number are 2 so it cannot be divisible by 3. Therefore it is not possible to fairly decide between 3 possible outcomes for any given finite N.

Is there any flaw in my reasoning?
Anonymous
August 11, 2005
The pragmatic answer? The question as posed is impossible, there has to be some tradeoff if the decision is to be made. One can either decide the timeframe in which the decision must be made and accept the resulting bias or decide the minimum acceptable bias and thereby determine the maximum timeframe. No matter how small the acceptable bias, provided it is not zero, it is possible to determine a time frame in which the question can be answered within the acceptable bias.
Anonymous
August 11, 2005
Since you can't evenly divide 2^N by 3, I would probably flip the coin once and use its final settled orientation to make the decision. If the angle were 0-120 degrees from a predetermined start angle I'd go with 'a', 120-240 I'd use 'b', 240-360 I'd use 'c'.

You could also time how long it takes for the coin to settle after leaving your hand and mod the milliseconds by 3 to get a result.

Finally, since we have infinite budget but limited time, we could flip the coin and mod the force at which it hits the ground (or its peak height in cm) by 3 for a result.

Then again, your mileage may vary depending on whether you're using African or European coinage.
Anonymous
August 11, 2005
Easy!

Make a funnel with three equally sized compartments at the bottom. Put A, B and C each in its own compartment.
Throw the coin in the funnel.
Pick the object from the compartment where the coin landed.

Cheers,

Erno
Anonymous
August 11, 2005
My 2c (Excuse the pun)

Assign 2 options to one side and one to the other. All have an equal chance of winning initial toss. If winning side has 2 options then toss again to pick winner.
Anonymous
August 11, 2005
As Devid has pointed out - this is impossible to do in definitely finite amount of time.
Suppose this will be requere at most N coin drops.
This lead to 2^N possible outcomes.
Even in case we will chose item before N-th drop - we can assume that all outcomes of drops after selection done lead to item we have choosen.
This mean that we have to divide 2^N possible outcomes to 3 equal groups - but this is impossible.

But algorithm pointed out by Ariel will most-likely finish in finite time. Probability that it will NOT finish in 2N drops is 2^(-2N).
Anonymous
August 12, 2005
Impossible? Why is everyone focusing on the "perfect" solution = there is a perfectly fair and pragmatic solution.

You throw the coin twice, giving you two binary digits.

HH : pick option 1
HT : pick option 2
TH : pick option 3
TT : Do the whole process again

While it's mathematically not "guaranteed" to finish - in practice it's very very likely to give you a solution, and it will always be fair.
Anonymous
August 12, 2005
The comment has been removed
Anonymous
August 12, 2005
Easy...flip the coin 3 times. Flip 1 is for A, flip 2 is for B, flip 3 is for C. Whichever flip is heads goes to the next round.

After round 1, there will either be a clear winner or 2 winners. (50% chance for 3 flips to be heads would say that there would be 1 or 2 heads flipped out of 3).

If there needs to be a round 2, 50% chance says that one of the two winners will become the clear winner.

Note: I'd like to see the coin that is 50%/50% fair ;)
Anonymous
August 12, 2005
The comment has been removed
Anonymous
August 12, 2005
A fair coin with no bias cannot be shown to exist. All that might be demonstratable is that the coin can be shown to have a worst a negliable bias within some meaning of negliable.

Using the same definition of negliable it would be possible to make the decision by sufficient throws.

Continuing beyond that point is meaningless because the inherent bias of the coin will have already caused any bias introduced by the method to be not significant. Thats the real world solution.

The mathematical solution is something else again. To get it done mathematically in a finite time just half the time it takes to toss the coin every time you throw it. The fact that that's impossible in the real world is not relevent because a coin with no bias is also impossible in the real world.
Anonymous
August 12, 2005
I would do it as follows. Basically, assign heads a weight of 1, and tails a weight of 0. Flip the coin three times, corresponding to the three sizes, and note the weights. At the end of the first round, if one side has a greater weight than the other two, then you have your choice. Otherwise, go to round two, flipping the coin once per side. Add that weight to the weights from the previous round(s). If there is one clear outcome, then that is the side. Continue until there is one clear winner.

This has the potential to go on forever, but you don't have a choice.

Personally, I like the funnel solution the best.
Anonymous
August 12, 2005
Hmm I am refining my code Actually this can be done for any number the more I think about it. And well me using 12 above should really be 6. You should find the least common multiple of 2 and X where X is the number you want to fairly roll.

So a better method to replace thw one above would be
class Class1
{
[STAThread]
static void Main(string[] args)
{
Console.WriteLine("Random Numbers for 3");
for (int LoopCount = 0; LoopCount < 30; LoopCount++)
{
//sleeping the thread because the random class is based on PC clock time
System.Threading.Thread.Sleep(500);
Console.WriteLine(getfairRandom(3));
}

Console.WriteLine("Random Numbers for 7");
for (int LoopCount = 0; LoopCount < 30; LoopCount++)
{
//sleeping the thread because the random class is based on PC clock time
System.Threading.Thread.Sleep(500);
Console.WriteLine(getfairRandom(7));
}

}

static private int getfairRandom(int MaxNumber)
{
int lcm = 2 * MaxNumber;
System.Random rndm = new Random();
double randomReturn = rndm.Next(1,lcm);
return Convert.ToInt32(Math.Ceiling(randomReturn / 2));
}
}
Anonymous
August 12, 2005
Oh I could refine it like right now if you send an even number to it it will multiply it times 2 however this gets you the rough idea. This is also not calculating the LCM for every number combination the LCM for 2 for any number not even is going to be 2 * X.
Anonymous
August 12, 2005
Throw the coin three times, there are 8 possible outcomes
000
001
..
..
111

Throw the coin two times, there are 4 possible outcomes
00
01
..
11

So now you have a total of 12 outcomes which is divisible by three.

Am I wrong?
Anonymous
August 12, 2005
Well the office here is stumped. I'm leaning towards unsolvable without "outside influence", as no power of 2 is ever divisible by 3.

(Prime factorization of any power of to is a list of twos, and in order to be divisible by 3, a 3 has to appear in there somewhere).
Anonymous
August 12, 2005
Deposit the coin in your bank account. Paypal the value of the coin to my Paypal account. I'll tell you which ball to pick. I'll be fair.

Or I like Raj's approach, which I'll just expand. Assign each ball a specific range: 0-3 4-7 8-11

Then throw the coin 3 times, which creates a binary number 000 to 111 (0 to 7 in decimal). Then throw it two times to create another binary number 00 to 11 (0 to 3).

Sum these two binary numbers. Then see which ball's range that number falls into.
Anonymous
August 12, 2005
The problem with the two seperate rolls method is you do not have a consistent probability. For instance. There is only 1 way to get 1, assuming 0-7 on the first run, and 1-4 on the second. However there are 2 ways to get 2. 1, 1 or 0, 2. So that doesn't work.
Anonymous
August 12, 2005
I think I am pretty sure I have it, with my code above it could be reduced to 2 simple lines.

System.Random rndm = new Random();
return Convert.ToInt32(Math.Ceiling(rndm.Next(1,(2 * MaxNumber)) / 2));

Basically what it does is say you supply 3 as you want it as a randome number the least common Multiple of 2 and 3 is 6 which any number in 6 has an equal chance of being picked if you roll a 6 sided die. However then you have to take the number picked and divide it by 2, this could give you a decimal so you have to use rounding toward positive infinity.

So say you get a 1 or a 2 then you dive that by 2 and you get a .5 or a 1.0 rounding up you get a 1, same thing for the rest of the numbers.

7 works the same way, (7 * 2), then get a random number out of 14, divide that number by 2 then round up.
Anonymous
August 12, 2005
The comment has been removed
Anonymous
August 12, 2005
The comment has been removed
Anonymous
August 12, 2005
The comment has been removed
Anonymous
August 12, 2005
Hrm, no, I take that back. Hastily thought out and gives undue precedence to b.
Anonymous
August 12, 2005
Ignore the previous one I posted...

Take a piece of paper, draw a circle. Divide it into three parts. Put the coin vertically at the center of the circle and give it a spin. The area that the coin covers most when it lands is the item that gets picked.
Anonymous
August 12, 2005
Hmmm. "Instead, you have a fair two sided coin. Note: 'fair' means 'comes up heads 50% of the time, and tails 50% of the time'."

Based on this statement if you throw the coin 2 times there is only 2 possible outcomes : HT and TH. Since by definition the coins comes up heads 50% or the time and tails 50% of the time.

So toss three times. You will always get either two heads in the set or two tails. (H = 2 and T = 1) or (H = 1 and T = 2)

A B C
T H T
2 1 2

A B C
H T H
2 1 2

an so on...

The item selected is the one with the 1 value.
Anonymous
August 12, 2005
I spoke too soon. I had a misunderstanding of the word "Fair". A math guru here at work pointed it out that fair only applied to an infinite series and not a finite one like I posted.
Anonymous
August 12, 2005
Last post for me:

stats for 1 million "tosses"
a:333388 b:332944 c:333668

public static string TossCoin()
{
int a = 0;
int b = 0;
int c = 0;
string selectedItem = string.Empty;
while(true)
{
a += TossOutcome();
b += TossOutcome();
c += TossOutcome();

if ((a != b) && (a!= c) && (b!=c))
{
selectedItem = (a > b)? ((a > c) ? "a" : "c") : ((b > c) ? "b" : "c");
break;
}
}
return selectedItem;
}

public static int TossOutcome()
{
byte[] b = new byte[1];
new RNGCryptoServiceProvider().GetBytes(b);
return (b[0] > 127)? 1 : 0;
}
Anonymous
August 12, 2005
I think this is an impossible problem, like writing 1/3 in base ten 0.3333333 it has to run infinitely. This problem is like trying to write one third in base two.

Once you make a choice of something to be less than perfect, you can "round it off" and get close enough for most purposes, but the perfect solution is infinite.
Anonymous
August 12, 2005
(1)Assign the sides values of 1 and 0.
(2)Toss the coin 3 times, and record the value as three digits - e.g. 111 or 110 and so on
(3)Repeat (2) and record again.
(4)compare the results of (2) and (3) on a column by column basis, and assign either A, B, or C depending on which column is the odd man out, reserving the cases which come up 111 or 000. [So 111 and 110 comes out 001 or C. You will get A, B, and C each occuring 8 times, with 12 left over values]
(5)of the reserved values, discard the second series.
(6) of the first series, if the first two columns are both "1", assign a value of "A" [you get 11 4 times]
(7) else if the first column is 0 assign a value of "B" [ you get this 4 times]
(8) else if the first column is 1 assign a value of "C" [ you get this 4 times].

A B and C now all have equal probabilities of occuring. I'm sure there is a more clever way to express this with exponents and roots, but I can't for the life of me think what it is.
Anonymous
August 12, 2005
I realised I was a little unclear - in (5) when I said discard the second series I meant the number you recorded in step (3), the remainin steps apply only to the number you recorded in step (2)
Anonymous
August 12, 2005
The comment has been removed
Anonymous
August 12, 2005
Think of it as a tournament.
a and b compete until one of them gets heads.
this "winner" competes against c until one of them gets heads.
Anonymous
August 12, 2005
ok i'm wrong
Anonymous
August 12, 2005
Is there another/better solution, anyone?
Anonymous
August 12, 2005
How about we combine my solution (actually, Ariel found mine in the 1st reply) and Andy White's? Would that make any difference?

---------------------------------------
1. Throw the coin twice.
2. if throws were "h-h" select 'A'
else if throws were "h-t" select 'B'
else if throws were "t-h" select 'C'
else if throws were "t-t", then:
- set A=h and B=t
- throw and select winner
- set winner=h and C=t
- throw and select winner
Anonymous
August 12, 2005
After reading through every answer, it's really really interesting. Imagine if there's a website posting a brainteaser everyday and gets educated answers from hundreds of thousands people everyday. Analyzing those answers would be amazingly cool, huh? A correct solution isn't the best solution, so the more the better! What's your solution?
Anonymous
August 12, 2005
I've been reading through the solutions and the "tournament" variation seems the most likely to produce a finite solution:

Toss 1: A meets B (50%/50%)
Toss 2: Winner meets C (50%/50%)
If Winner wins again, no more tosses.
Toss 3: If C wins, C meets Loser (50%/50%)
Whoever wins Toss 3, gets it.

This is a finite loop. All participants have the the odds of winning at 50% each time they play (each plays twice at most), however there is no replay once a winner is decided.

Given a tie, It revolves around who wins last.
A & B -> A & C -> A
A & B -> A & C -> C & B -> C
A & B -> A & C -> C & B -> B
A & B -> B & C -> B
A & B -> B & C -> C & A -> C
A & B -> B & C -> C & A -> A

Since there is a variable 2 OR 3 rounds, the 2^N problem is resolved down to 6 possible outcomes, divisible by 3 and 2. A & B Always start.

I think this is it? Any care for peer review?
Anonymous
August 12, 2005
Well, the problem appears to be tied into the probabilities of the combinations appearing. So why not just modify the equation to deal specifically with the probabilities?

Out of 2 throws, you get something like:

HH = 25%
TH or HT = 50%
TT = 25%

So, the setup could use weights. When you get HH add a weight of 2 for A. When you get TH or HT add a weight of 1 for B. When you get TT, add a weight of 2 for C.

Now, you just need to do pair throws for whatever finite number of times makes you happy that the statistics balance out. (Didn't do the math, but I'm guessing it would be a small number -- maybe 10 pair throws?).

If I'm way off here, could someone tell my why?
Anonymous
August 12, 2005
when it gets to 50 replies, could you give us a remote hint?
Anonymous
August 12, 2005
brainteasing resumed, i'm trying to think in a different direction. So how about this?

Let A=h, B=t.
With my eyes closed, throw the count and guess whether H/T is selected. If the guess is right, pick C, otherwise, pick whatever the coin selected for you
Anonymous
August 12, 2005
wait a minute, I'm afraid my brain is biased and would always pick A over B, so let's just throw a second time and let the 2nd result be my guess (so if both throws yield the same H or T, pick C, otherwise pick the 1st result)
Anonymous
August 12, 2005
ok, both of my last 2 posts were wrong because C would get 50& chance to be picked
Anonymous
August 12, 2005
The comment has been removed
Anonymous
August 12, 2005
Ed Kaim & Erno: Love your answers :)
Anonymous
August 12, 2005
Daniel: "The mathematical solution is something else again. To get it done mathematically in a finite time just half the time it takes to toss the coin every time you throw it. The fact that that's impossible in the real world is not relevent because a coin with no bias is also impossible in the real world. "

We're talking about the mathematical world here.

And it's not time that we're measuring. We're asking if the algorithm will "terminate" or not.

i.e. it's not valid to say: i have a computer that takes no time to do anything. So no matter what it will always finish immediately, even if it takes infinitely long because it's an instantaneous computer

:)
Anonymous
August 12, 2005
We seem to have some differing of opinion on this.

Some people think that it must be impossible as given any set time that the algorithm must terminate, you cna show that there is a probability (however unlikely that it migth take that long).

However, others have shown that regardless, it can't take forever, and thus must eventually end at some point.

Can these ideas be reconciled. Does either imply the existence of (or lack thereof) of a suitable algorithm that can solve the problem requirements?
Anonymous
August 12, 2005
i think i got it this time

a.value = b.value = c.value
countToException = 0

do {
a.face=h
b.face=t

if throwCoin()==h then a.value++
else if throwCoin()==t then b.value++

//if countToException == 1000 then break

b.face=h
c.face=t

if throwCoin()==h then b.value++
else if throwCoin()==t then c.value++

c.face=h
a.face=t

if throwCoin()==h then c.value++
else if throwCoin()==t then a.value++

}while(a.value==b.value && b.value==c.value)

return MinOrMax(a,b,c) //take the single one, min or max

there's still a chance that a.value== b.value== c.value always. So, I wanted to include the countToException inconveniently to just decide the result btwn a & b.
Anonymous
August 12, 2005
couldn't think about the funnel, but i thought about the angle and the milisecond ones, although they would need additional equipments to carry out. and the latest solution was an improvement from Andy White's a&b-b&c-c&a algo, or so i thought. good night.
Anonymous
August 12, 2005
The comment has been removed
Anonymous
August 12, 2005
Hmm - just ran an exhaustive search on possible partitionings of bernoulli distributions for N < 30.

For N<30, no combination of toss count frequencies sums up to 1/3.

(its fortunate that python enables unlimited precision maths)

fact = [1]100;
for i in range(1,len(fact)): fact[i] = i * fact[i-1]

def b2(n,N): return (fact[N], fact[n] * fact[N-n] * N**2)

def add((n1,d1), (n2,d2)): return (n1d2 + n2d1, d1d2)

def combsum(c, (a,b), i, N):
for j in range(i,N):
c.append(j)
(x,y) = add((a,b), b2(j,N+1))
if (y == 3x): print c
elif (y > 3x): combsum(c, (x,y), j+1, N)
c.pop()

for N in range(2,50):
print N
combsum([], (0,1), 0, N)
Anonymous
August 13, 2005
2 throws are required.

The first throw is to determine whether its for A or B.
Event(A|B) -> x

The second throw is to determine if its the outcome of the first throw or C.
Event(x|C) -> winner
Anonymous
August 13, 2005
All "tournament" variations of a solution are incorrect since this will give the first two combatants advantage since they will always be given a second chance (in case the loser goes against the third), or disadvantage (in case the winner goes against the third).

Experiment with a few million tosses will give C a 25% chance of being selected in a tournament where the loser of A and B goes against C. C will be given a 50% chance in a tournament where the winner goes against C.
Anonymous
August 13, 2005
i implemented my last algo, ran it for a couple million times. The average seemed about right. (exception never occurred)
Anonymous
August 13, 2005
Loc: Does your algorithm terminate?
Anonymous
August 13, 2005
at least it did for the last 100 million times i tested. but no, the algo may not terminate in a special case.

but i'm sure that there's something else more efficient/simple/elegant than mine
Anonymous
August 13, 2005
In my tournament idea, there are only two "matches" to declare a winner.
A against B
Winner against C
Anonymous
August 13, 2005
Andy, your tournament gives C 50% to win. The regular tournament would be

A -
-- W1
B -

C -
-- W2
D -

then W1 vs. W2
Anonymous
August 13, 2005
loc you are right.

I am worthless.
Anonymous
August 13, 2005
The comment has been removed
Anonymous
August 13, 2005
man, the previous answer gives B 50% chance.
Anonymous
August 13, 2005
The comment has been removed
Anonymous
August 13, 2005
there are 8 outcomes, not 1 but 2 of them are undecided (no tail, and all tails)

therefore, your solution is the same as the hh,ht,th,tt where tt is "play again"
Anonymous
August 13, 2005
loc, thanks for pointing that out.
To make it finite, how about we keep track of how many times each member has thrown tails. If a round repeats, we count how many times they have thrown tails, in previous rounds (with same member count) and whoever has most tails gets eliminated.

This is the opposite of the source code I posted earlier where whoever has the most heads wins.

Oh..well.
Anonymous
August 13, 2005
I don't see why this thread didn't end when someone posted the rotational answer. It's simple and effective and finite.
Anonymous
August 13, 2005
This is what i had that works. I need to prove it terminates though.

public static int Pick(Item A, Item B, Item C)
{
int count = 0;
do
{
A.Face = 1;
B.Face = 0;
if (Program.ThrowCoin()==1)
A.Value++;
else
B.Value++;

count++; //if (count==1000) break

B.Face = 1;
C.Face = 0;

if (Program.ThrowCoin()==1)
B.Value++;
else
C.Value++;

C.Face=1;
A.Face=0;

if (Program.ThrowCoin() ==1)
C.Value++;
else
A.Value++;
}
while(A.Value==B.Value && B.Value==C.Value);

return MinOrMax(A, B, C);
}
Anonymous
August 13, 2005
I can prove that that could not terminate: if Program.ThrowCoin() always returns 1, then you'll never break out of the while loop. QED.

Sigh... I know I've ranted a bit about the CS curriculum of our alma mater being too focused on theory at the expense of actual programming, but now I see some wisdom in it.
Anonymous
August 13, 2005
Slusky: "I can prove that that could not terminate: if Program.ThrowCoin() always returns 1, then you'll never break out of the while loop. QED. "

Can Program.ThrowCoin always return 1?
Anonymous
August 13, 2005
DrPizza: "I don't see why this thread didn't end when someone posted the rotational answer. It's simple and effective and finite. "

because it measures properties that aren't available on the coin provided. All you can do is flip it and find out if it was heads or tails.
Anonymous
August 13, 2005
Loc: "This is what i had that works. I need to prove it terminates though. "

Does it terminate?
Anonymous
August 13, 2005
It does terminate. The only ways it doesn't is when ThrowCoint() returns:

1 1 1, 1 1 1, ...

or

1 1 1, 0 0 0, ...

or

0 0 0, 0 0 0, ...

For case 1 and 3, it doesn't seem like the coin is perfectly fair.

For case 2, you might argue that it seems FAIRER over 6 throws, but 3 same results in a row proves the coin is not PERFECTLY fair. oooh my reasoning in this part is not very strong...
Anonymous
August 13, 2005
No, actually Ariel got it right in the very first reply:

HH -> 1
HT -> 2
TH -> 3
TT -> play again

It is finite because if it doesn't terminate then the outcomes will always be Tail, which is not possible for a FAIR coin.

Final answer.
Anonymous
August 13, 2005
Loc: "It is finite because if it doesn't terminate then the outcomes will always be Tail, which is not possible for a FAIR coin.

Final answer. "

So when does it terminate?
Anonymous
August 14, 2005
Since the coin is precisely fair, it terminates within 4 rounds
Anonymous
August 14, 2005
never mind that answer, that's my 1st thought when i woke up today.

how about within 8 rounds (16 throws)
Anonymous
August 14, 2005
Loc: In 8 rounds (presuming 2 flips per round), it's completely possible with a fair coin to get:

t t t t t t t t t t t t t t t t

There's a: 1/(2^16) chance of that happening. Unlikely, sure, but it's still quite possible that with your algorithm it won't terminate within that number of throws.

Remember, a "fair" coin doesn't mean: "given 2n tosses of the coin, n must be heads and n must be tails". It means that given any toss of the coin (which is independent of any other toss), there's an equal chance of heads or tials coming up.
Anonymous
August 14, 2005
"because it measures properties that aren't available on the coin provided. All you can do is flip it and find out if it was heads or tails. "
But that's not what the question says!

Perhaps you do not have a coin at all but rather a disc with each side painted a different uniform colour?
Anonymous
August 14, 2005
Pizza - the coin is fair as far as coming up heads or tails goes. Its fairness as far as rotation goes is unknown.

Cyrus - does this puzzle have a solution? Seems to me that it doesnt.
Anonymous
August 14, 2005
I had the same solution as Ariel. You can easily show that the answer will pop out in an expected number of 24 throws, with a standard deviation of about sqrt(1200)=36.641 (unless, I made a mistake :) ).

It is possible for this algorithm not to terminate, even if the probability of this event is zero. (probability(event) == 0 does NOT mean it is impossible).
Anonymous
August 14, 2005
So my precision is only up to 0.0000152587890625. But the algorithm is obviously converging, so it can terminate.

http://en.wikipedia.org/wiki/Termination :
"In essence, the problem is that an algorithm for computing a real number to infinite precision would never terminate. However, practical algorithms can all be shown to converge, thus, they can be made to terminate simply by accepting a limit on the achievable precision of the computation."
Anonymous
August 14, 2005
To those who think it's fine to have an algorithm which usually terminates 'quickly' (within a few hundred throws), it's not.

If the possibility of your algorithm taking over million throws is one in a million, and you run it a million times a day (this happens with software, you know?) then, on average, once a day, you'll have to sit and wait for over one million throws.

Of course the coin toss is just an example: we could be talking about an algorithm which needs to communicate over TCP, hit a database, or even simply cause a context switch.

If the algorithm has a terrible worst case run time, then you could be in trouble. That's why it's important to find algorithms which can be proven to terminate within finite time.

Thanks for the illustration Cyrus.
Anonymous
August 14, 2005
Rik, of course you are right. But your analysis is of a different algorithm complexity.

In this case, if a flip takes one microsecond then you'll have to run the algorithm about 1000...00 times - with 666666 zeros -- to see a runtime greater than one second. In other words, you'll need to wait for the universe to die, unless you are really unlucky.
Anonymous
August 15, 2005
Of course, you can also bound the number of trials:

string choose()
{
for (int i = 0; i < 1000; i++)
switch (flip()<<1 | flip())
{
case 0: return "A";
case 1: return "B";
case 2: return "C";
}
return "C";
}

Guaranteed to terminate, fair to 1 part in 4**1000, i.e. more fair than any possible feat of physical engineering could possibly achieve, and more fair than any statisical measure could possibly detect.

Remember that the coin is fair, so that means that saying "what if the coin always comes up heads" is changing the premise to test the algorithm. If the coin always comes up heads, then there is no possible algorithm that can produce a fair result.
Anonymous
August 15, 2005
The comment has been removed
Anonymous
August 15, 2005
The comment has been removed
Anonymous
August 16, 2005
Flip the coin 3 times, assign heads=1 and tails=0

Place the result of the first toss in the 4's bit, the second in the 2's bit and the third in the 1's bit to get a decimal number between 1 and 8, called T.

T is the number of times you will again flip the coin. Again assign heads=1 and tails=0, but now ADD your results to get S, a number between 0 and 36.

The result is S % 3.
Anonymous
August 16, 2005
David, T would be a number from 0..7. So you'd need to add one first.

The problem lies with S, though. Adding your results for T flips with H=1 and T=0 would give a number ranging from 0..T-1, not 0..36.

Finally, 0..36 has 37 items, which is not divisible by 3.
Anonymous
August 16, 2005
Oops, that's 0..T, not 0..T-1.
Anonymous
August 16, 2005
I'm with johnfisher,

tt-25%
ht or th-50%
hh-25%

Assign tt-a, ht or th-b, and hh-c.

Any time a tt or hh comes up, give a or c 2 points and any time a th or ht comes up give b 1 point. This is statistically fair and simple. After reading all posts and seeing the flaws in all of them, I have to say this is the best solution.
Anonymous
August 16, 2005
Derek and JohnFisher

The problem with your solution is that it runs the risk of never giving a final answer. What if, after your finite number of throws, two or all alternatives have the same score?
Anonymous
August 16, 2005
The comment has been removed
Anonymous
August 17, 2005
Gonna have to go with playersnoopy on the whole "where's the answer" business. You've had you fun, watching us squirm. Now we demand recourse :p.
Anonymous
August 17, 2005
Cyrus, if you do have the solution that ever halts (although i'm leaning toward that it doesn't), don't give it out yet. one more day. I can't remember a puzzle that struggles me this long. Maybe I've lost "it".
Anonymous
August 17, 2005
You can have an effectively 3 sided die by marking two faces of a die with 'a', two faces with 'b' and two faces with 'c'.
Anonymous
August 17, 2005
I still like the hh,ht,th,tt one, with an improvement: if tt the first time give bonus 1 point, if next round is aslo tt, give bonus 2 pts, if the 3rd round is also tt, give bonus 3 pts. now the result will be decided by the bonus pts mod 3.

Can anyone prove that the bonus system is not fair?

==================================

bonus = 0
result = ThrowTwice();
if (result==tt){
bonus = 1;
result = ThrowTwice();
if (result==tt){
bonus = 2;
result = ThrowTwice();
if (result==tt){
bonus = 3;
}
else { return DECIDED_RESULT; }
}
else { return DECIDED_RESULT; }
}
else { return DECIDED_RESULT; }

return bonus % 3;
Anonymous
August 17, 2005
Just a tweak

bonus = 0
result = ThrowTwice(); //can be 0, 1, 2, or 3
if (result==3){
bonus = 1;
result = ThrowTwice();
if (result==3){
bonus = 2;
result = ThrowTwice();
if (result==3){
bonus = 3;
}
else { return result % 3; }
}
else { return result % 3; }
}
else { return result % 3; }

return bonus % 3;
Anonymous
August 17, 2005
never mind, bonus will be just 3...

what am i thinking? it won't keep me awake tonight anymore.
Anonymous
August 17, 2005
The solution involves a 2 step process (i.e. finite).

Let's say we have 3 candidates, A, B and C. We want to use the coin to randomly select one of them.

Round 1: Elimination Round

Throw the coin twice. Possible outcomes:
HH HT TH TT

If HH or HT, candidate A goes through
If HT or TH, candidate B goes through
If TH or TT, candidate C goes through

As you can see, two random candidates will go through to round 2

Round 2: Select Winner

Now it's trivial. You have two candidates to select from, and a coin that can choose for you.
Anonymous
August 17, 2005
The solution involves a 2 step process (i.e. finite).

Let's say we have 3 candidates, A, B and C. We want to use the coin to randomly select one of them.

Round 1: Elimination Round

Throw the coin twice. Possible outcomes:
HH HT TH TT

If HH or HT, candidate A goes through
If HT or TH, candidate B goes through
If TH or TT, candidate C goes through

As you can see, two random candidates will go through to round 2

Round 2: Select Winner

Now it's trivial. You have two candidates to select from, and a coin that can choose for you.
Anonymous
August 17, 2005
Dodgy - if you throw HH or TT, only one candidate will go through, and the probabilities of selecting a/b/c arent fair.

Do they not teach basic statistics in school these days? Im asking, because it seems that so many people throwing out solutions to this question are making very basic mistakes.
Anonymous
August 17, 2005
Doub! Found an obvious problem. If HH or TT then only one candidate goes through. :(
Anonymous
August 18, 2005
How silly of me. Even if you could select two members at random for elimination, you've already solved the problem. The remaining candidate might aswell be the winner.

Show us your 10c damien or are you risking making a basic mistake?
Anonymous
August 18, 2005
DodgyRabbit: A and C can win at first round, B cannot. Your system is not giving equal weight to each candidate.
Anonymous
August 18, 2005
Cyrus, I don't think your understanding of the definition of the word Algorithm is correct. An algorithm doesn't have to terminate in finite time.

i.e. "a finite set of well-defined instructions for accomplishing some task which, given an initial state, will terminate in a corresponding recognizable end-state"

"A finite set of well-definied instructions" means that the set of instructions is finite not that the time taken is finite.

In the first comment, the set of instructions is 4, not infinite.

The probability of this never terminating tends to zero.

However, that problem is not interesting. The interesting one is the one that definitely terminates in finite time.
Anonymous
August 18, 2005
Dodgy - appologies for seeming to direct my statistics question at you - it was a more general observation.

I actually did give an answer above, but I had to redefine 'fair' to be 'fair within some tolerance' in order to do it.

So your elimination aproach can be modelled as throwing two coins followed by a third, where sometimes the third coin toss is irrelevant, for a total of 3 coin tosses. Heres how your algorithm breaks down:

HHH: A
HHT: A
HTH: A
HTT: B
THH: B
THT: C
TTH: C
TTT: C

As you can see, given an equal probability of any of those 8 choices coming up, the choice of A, B, or C is made in a ratio of 3:2:3.

As far as I can tell, theres no exact solution to this problem. No matter how many coin tosses you make, any given sequence of toss results or combination of sequences of toss results will have a probability that is expressed as n/N^2, where n is any number, and N is the number of tosses. n/N^2 != 1/3 for any integer n or N.
Anonymous
August 18, 2005
The comment has been removed
Anonymous
August 18, 2005
The comment has been removed
Anonymous
August 18, 2005
The comment has been removed
Anonymous
August 19, 2005
The comment has been removed
Anonymous
August 19, 2005
The comment has been removed
Anonymous
August 19, 2005
Smarmy: Ah, but the 2 tosses are within the 3 tosses. therefore, you have 12 possibilities with 3 tosses instead of 8.

A can win 4 ways, B can win 4 ways, C can win 4 ways.

;)
Anonymous
August 19, 2005
TimW, each can win in 4 ways, but each of those ways does not have equal probability.

This is impossible to do with a bounded number of flips. Here is a proof:

Using Cyrus’s definition of algorithm, we must be able to select from a, b, and c using a bounded number of flips.

Let N be the upper bound of the number of flips required for our input size of 3 (i.e. the 3 items a,b,c).

Let x = x_1, x_2, …, x_n be the sequence of heads or tails values produced by flipping the coin N times.

Let f(x) be any algorithm that takes as input an N length sequence of heads or tails values to produce an output of a or b or c.

Since each element of x has two possible values and x has N elements, we know that there are 2^N possible values for the entire sequence x. Furthermore, since a fair coin is deciding the value of each element of x with equal probability for heads or tails, we know that the probability of any one of these 2^N sequence values occurring must be 1/(2^N).

The probability of any output (a or b or c) occurring is equal to the sum of the probabilities of the inputs to f(x) that produce that output. Since all inputs have a probability of 1/(2^N) and since any finite sum of such probabilities can never be 1/3 (I can prove this separately if anyone doesn’t believe me), there is no bounded time algorithm that can use a fair coin to fairly select among three options.

-Scott
Anonymous
August 19, 2005
TimW:

You are right, since the results of the 3 toss round are dependent on the results of the 2 toss round, the actual probabilities are different than I suggested:

Listed are the possible tosses enumerated with the winners of the 2 toss and 3 toss respectively:

HHH = C C
HHT = C B
HTH = C A
HTT = C B
THH = C A
THT = C B
TTH = B A
TTT = B A

C will win 43.75% of the time, B will win 31.25% of the time and A will win only 25% of the time. The probabilities are not at all equal.

Though all this is meaningless because I think Scott and Dan are right that there is no correct answer.
Anonymous
August 19, 2005
And by different I mean exactly the same. :)
Anonymous
August 19, 2005
Scott, I agree that 2^N % 3 will always be 1 or 2, for all N. But my point is that (2^N)/3 will get large enough such that 1/((2^N)/3) can be neligible. In theory, it can't be achieved. But in real life, I would tolerate a fairly fair solution.
Anonymous
August 19, 2005
The comment has been removed
Anonymous
August 20, 2005
The comment has been removed
Anonymous
August 20, 2005
The comment has been removed
Anonymous
August 20, 2005
The comment has been removed
Anonymous
August 20, 2005
"But in real life, I would tolerate a fairly fair solution."

loc, it doesn't matter what you would tolerate in real life. Cyrus is the one asking the question. :-)

While it is framed as a toy problem, building algorithms that can do this is very important in cryptography and several other fields. I think that Cyrus's point here is to get people to think deeply about what is and isn't possible. That means being rigorous about what is asked for and is being delivered. Is a bias of 1/2^128 acceptable? I don't know, since I don't know what the application is, but being upfront about the bias enables you to decide. Is an unbounded algorithm with an expected iteration count of 4/3 (i.e. 8/3 flips) acceptable? I don't know, but understanding the runtime characteristics of the algorithm is the first step to finding out.

Cyrus originally asked for a fair (not fairly fair) bounded time algorithm. I proved that he can't have that, because it is impossible.

Then we came to a question about unbounded time algorithms and expected value. I derived the required EV.

The third option is to accept a biased selection algorithm that runs in bounded time. Have we been rigorous enough about the characterstics of that option? What questions should we be asking and what are the answers to those questions?

-Scott
Anonymous
August 20, 2005
"But in real life, I would tolerate a fairly fair solution."

loc, it doesn't matter what you would tolerate in real life. Cyrus is the one asking the question. :-)

While it is framed as a toy problem, building algorithms that can do this is very important in cryptography and several other fields. I think that Cyrus's point here is to get people to think deeply about what is and isn't possible. That means being rigorous about what is asked for and is being delivered. Is a bias of 1/2^128 acceptable? I don't know, since I don't know what the application is, but being upfront about the bias enables you to decide. Is an unbounded algorithm with an expected iteration count of 4/3 (i.e. 8/3 flips) acceptable? I don't know, but understanding the runtime characteristics of the algorithm is the first step to finding out.

Cyrus originally asked for a fair (not fairly fair) bounded time algorithm. I proved that he can't have that, because it is impossible.

Then we came to a question about unbounded time algorithms and expected value. I derived the required EV.

The third option is to accept a biased selection algorithm that runs in bounded time. Have we been rigorous enough about the characterstics of that option? What questions should we be asking and what are the answers to those questions?

-Scott
Anonymous
August 21, 2005
Scott, I fully aware that he asked for a perfectly fair solution. I had admitted that it's not possible to come up with.

My last solution is just kind of a bonus answer outside of his question, like "hey since we can't do it, maybe we can do this (if we ever had to) because it's very close to what you asked". =)
Anonymous
August 21, 2005
By the way, I really like the helpful posts you have contributed, Scott.
Anonymous
August 22, 2005
Hi

what about converting the results from heads/tails trial to an int? [as in SelectNextItem() below]. The test code I left in as I used it for evaluation, and the chances of a, b or c beeing selected should be very close to equal (that is of course if I am not mistaken ;-). Termination is guaranteed after 8 'flips' in this code.

MaLio

namespace HeadsTailsOutcomes {
/// <summary>
/// Summary description for SelectionTest.
/// </summary>
class SelectionTest {

// number of distinct items
private const int NUM_ITEMS = 3;
// number of iterations for testing
private const int NUM_ITERATIONS = 100000;
// random number generator
private static System.Random _Random = new System.Random();

/// <summary>
/// Main
/// </summary>
static void Main(string[] args) {

int[] items = new int[NUM_ITEMS];

for (int iteration = 0; iteration < NUM_ITERATIONS; iteration++) {
items[SelectNextItem()]++;
}

for (int index = 0; index < NUM_ITEMS; index++) {
System.Console.WriteLine("{0} has {1}", index, items[index]);
}

System.Console.WriteLine();
System.Console.ReadLine();
}

// SelectNextItem
public static int SelectNextItem() {

int evaluator = 0;

for (int i = 1; i < 9; i++) {
if (IsHeads) {
evaluator |= (1 << i);
}
}

return evaluator % NUM_ITEMS;
}

// IsHeads
private static bool IsHeads {
get {
return ((_Random.Next(int.MaxValue) % 2) == 0);
}
}
}
}
Anonymous
August 22, 2005
And scott wins the internet.
Anonymous
August 22, 2005
Was I right? I'm most curious ...

MaLio
Anonymous
August 22, 2005
Malio - yes, your algorithm is basically correct (though your code is awkward - using a property IsHeads instead of a function is bad style).

Flip a coin N times to create an N bit integer, then mod 3 to determine which of the 3 choices are selected. One choice will be advantaged by one part in 2^N.

Contrast this with the probablistic approach, which does pairs of flips to create numbers in the range 0..3, and terminates when a number in the range 0..2 is created. This requires an average of 8/3 coin flips to produce a result, and is fair to one part in 4^N, where N is the limit to the number of flip pairs you are prepared to consider. The average number of flips requied for a result is independant of the limit N, where N is large.
Anonymous
August 23, 2005
The comment has been removed
Anonymous
August 25, 2005
The Search feature on the upper right hand corner doesn't work. Searching for "problem" resulted in 7 pages, which all looked the same somehow. But then there's Google.
Anonymous
August 25, 2005
confirmed. paging doesn't work for any search
Anonymous
August 31, 2005
You ask for equal probability, not for being random.

I propose this algorithm:

1) select A
2) select B
3) select C
4) goto 1

You can use the coin to buy a soda.
Anonymous
September 14, 2005
The algorithm may actually take infinite time. There is no guarantee that a fair coin will ever come up heads, for example, even after an infinite number of tosses.
Anonymous
September 14, 2005
Herbie: Nope. The algorithm cannot take infinite time. It will always be finite and it will always terminate.

however, the time it takes is not bounded. There's a difference.
Anonymous
September 14, 2005
In an infinite sequence of coin flips, you may never see a terminating result, thus the algorithm will never terminate. Am I missing something here?
Anonymous
September 14, 2005
Sorry for the bluntness of the previous post, and perhaps I am misunderstanding your claim. I do agree that the algorithm is unbounded. I do not agree that it always terminates. Do you mean that the algorithm will "certainly" terminate (every outcome of coinflips will cause it to terminate), or that it will "almost certainly" terminate (the probability of termination is 1)?
Anonymous
September 14, 2005
Herbie: "In an infinite sequence of coin flips, you may never see a terminating result, thus the algorithm will never terminate. Am I missing something here?"

In an infinite sequence of coin flips you will see a terminating result. :)

"Sorry for the bluntness of the previous post, and perhaps I am misunderstanding your claim. I do agree that the algorithm is unbounded. I do not agree that it always terminates. Do you mean that the algorithm will "certainly" terminate (every outcome of coinflips will cause it to terminate), or that it will "almost certainly" terminate (the probability of termination is 1)? "

No, there is no probability going on. (well, not strictyly true. there is probability, but it's just uninterestingly: 1). The other place where probability came in is in the expected number of rounds necessary for it to terminate: 4/3

What is going on is that even in this perfect math world, it is provable (and has been done so in posts here) that the algorithm cannot take finite time to end. And, as has also been stated, a non-infinite (and thus finite) operation suffices for the term "algorithm".

What can also be shown is that you cannot state the bound on the algorithm. I.e. if you say that it will end in N steps, one can show that there is a probability (albeit low) that the algorithm might end up taking more than N steps. However, despite being bounded, it is still finite.

Remember, there is space between unbounded and infinite :)
Anonymous
September 15, 2005
The comment has been removed
Anonymous
May 31, 2009
PingBack from http://outdoorceilingfansite.info/story.php?id=1009
Anonymous
May 31, 2009
PingBack from http://outdoorceilingfansite.info/story.php?id=18645
Anonymous
June 01, 2009
PingBack from http://uniformstores.info/story.php?id=15297
Anonymous
June 08, 2009
PingBack from http://quickdietsite.info/story.php?id=4165
Anonymous
June 09, 2009
PingBack from http://insomniacuresite.info/story.php?id=7322
Anonymous
June 13, 2009
PingBack from http://firepitidea.info/story.php?id=1462
Anonymous
June 14, 2009
PingBack from http://patiocushionsource.info/story.php?id=2238
Anonymous
June 15, 2009
PingBack from http://mydebtconsolidator.info/story.php?id=3697

Share via

Heads, or Tails?

Comments

Additional resources