A Fair Decision with a Biased Coin

An eccentric uncle has left a fortune to you and your brother - with a very strange condition.

He's bequeathed to you his special fake coin that lands heads more often than it lands tails. And all his money will go either to you or to your brother depending on who wins a sequence of tosses of his special coin.

What method can you and your brother devise so that you'll both agree that a fair winner has been determined by repeated tosses of the biased coin? It's unlikely that more than 26 tosses would be required.

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

There should be a limitation on what method is allowed, otherwise I can do this without any toss:

I've set the coin to some face and hide it under the bowl, on the table in front of you. I'm not touching it any more. You must guess the face-up side. If you're correct, you win, otherwise I win.

Or easier:

Let's just take a fair coin.

On the other hand, if the method can't be just:

I'll pick a subset of the possible 26-coin sequences. You pick whether to take that subset or give it to me. We'll then toss the coin 26 times; if the resulting sequence appears in the subset, whoever has the subset wins, otherwise they lose.

Because the second player can just pick the one with all heads and have large probability of winning if the probability of heads is big, like, 99.9999% or something.

Ivan Koswara - 5 years, 5 months ago

Trust me. There is a solution based solely on tossing the biased coin. A solution that both brothers will accept as fair - even the brother that loses will agree that the process was fair.

I'll give a helpful hint in a couple of days.

Martin Coles - 5 years, 5 months ago

With that edit, the answer is obvious. (Toss the coin twice. If it's HT, first player wins; if it's TH, second player wins; if it's anything else, toss again.) I'm very sure the 26-toss mark can be easily passed, though; just try seeing what happens if the probability of heads is 99% ("much more often").

Ivan Koswara - 5 years, 5 months ago

Is the probability of landing on heads known or unknown?

Interesting problem! Can we make a fair outcome from biased outcomes?

Calvin Lin Staff - 5 years, 5 months ago

The probability of heads is not known.

Martin Coles - 5 years, 5 months ago

They can count how many times there was a heads on even tosses and odd tosses and see which one has more. Before they toss the 26 times, one of then will pick even and one will pick odd.

Josh Kari - 5 years, 5 months ago

What happens if there is a tie?

Ivan Koswara - 5 years, 5 months ago

This would work. However, there's a more elegant solution. I'll give you a hint. With this solution, the winner could be decided with as few as two tosses of the biased coin.

Martin Coles - 5 years, 5 months ago

I don't see how it works, since there is a possibility of a tie.

Ivan Koswara - 5 years, 5 months ago

@Ivan Koswara – The decision might be made after two tosses, but it might take more tosses. It's extremely unlikely that as many as 26 tosses would be required to determine the winner.

Martin Coles - 5 years, 5 months ago

@Martin Coles – "Extremely unlikely" is not "never". Your problem requires you to have the winner within 26 tosses; you're not allowed to go over, even if the probability that will occur is tiny.

Ivan Koswara - 5 years, 5 months ago

@Ivan Koswara – OK. Problem is hereby rewritten. Once the correct strategy has been adopted by the two brothers, it's extremely unlikely that more than 26 tosses would be required to determine the winner.

Martin Coles - 5 years, 5 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$