# Selecting randomly from five options, using only a coin **URL:** \ **Category:** Factual Questions\ **Created:** [May 7, 2006, 12:54am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714 "2006-05-07T00:54:41Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![Frylock](https://avatars.discourse-cdn.com/v4/letter/f/ce7236/32.png) [@Frylock](https://boards.straightdope.com/u/Frylock)\ **Post date:** [May 7, 2006, 12:54am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/1 "2006-05-07T00:54:41Z")
Suppose you have five options out of which you need to select one at random. Each is to have the same probability of being picked–i.e., one in five. The only means of randomization you have on hand is one which selects between _two_ equally probable options–say, a coin. I’ve been trying to figure out a way to do this. I think I did figure out a way, but its a little complicated, and involves a process which runs an (incredibly miniscule, but non-zero) chance of never coming to a conclusive end. (Hard to explain.) I was wondering if there’s a relatively simple method which I’m overlooking, and also whether there’s one guaranteed to end in a conclusive decision after a finite number of steps. -FrL- (The method I came up with is: Flip the coin ten times, recording the flips. Label each option with a letter, A through E. Now number A through D 1 through 4. Use the first two flips to decide between one of these 4. Now lable A through C 1 through 3, and lable E 4. Use the second two flips to decide between one of these 4. Now label them 1 through 4, this time skipping C. Decide between the 4. Now skip B, and decide. Now skip A, and decide. Now count up how many times each of A through E was selected. If any was selected more than all the others, then end the process–that one is your final selectee. Otherwise, there was a tie. It happens that the only possible ties inthis situation are 2-way and 5-way. If it was 5-way, strt over. If it was 2-way, flip the coin once more to decide between those two. That gives each possibility an equal probability, I think. But its minutely possible for the process to take a very long time.) ---
**Author:** ![zut](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/zut/32/2875_2.png) [@zut](https://boards.straightdope.com/u/zut)\ **Post date:** [May 7, 2006, 1:09am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/2 "2006-05-07T01:09:19Z")
Flip your coin four times. If if comes up all heads, start over. Otherwise: HHHT, HHTH, HHTT = option 1 HTHH, HTHT, HTTH = option 2 HTTT, THHH, THHT = option 3 THTH, THTT, TTHH = option 4 TTHT, TTTH, TTTT = option 5 There’s still some minimal chance of continuously flipping all heads for ever and ever, but I’m not so worried about it. ---
**Author:** ![elfbabe](https://avatars.discourse-cdn.com/v4/letter/e/b782af/32.png) [@elfbabe](https://boards.straightdope.com/u/elfbabe)\ **Post date:** [May 7, 2006, 1:12am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/3 "2006-05-07T01:12:14Z")
My friends and I do this sort of thing sometimes when we need to choose one of us to do something. I’ll explain how it’s run in that context. First, you give each of the five people a different number, 0 through 4. Then you convert those numbers into binary - 000, 001, 010, 011, and 100. (yes, several of us are computer science majors, why do you ask? 😛 ) Then we assign a digit, 1 or 0, to each side of the coin. Heads is generally 1. Someone flips the coin three times and records the results. If your number comes up, you’re it. If we get 101, 110, or 111, we have to do it over. This can be easily adapted for any number of people, but it works best for powers of two or numbers slightly less than powers of two. Otherwise, your chances of having to do it over get annoyingly high. In this case, you have a 3/8 = 37.5% chance of having to run a second round, a 14.0625% chance of having to run a third, an 8.4375% chance of having to run a fourth, etc. It’s faster if you use multiple coins (say, a dime, a nickel, and a penny) and designate which digit they represent so that you can flip all three at once. Yes, we are big nerds. ---
**Author:** ![Shagnasty](https://avatars.discourse-cdn.com/v4/letter/s/9dc877/32.png) [@Shagnasty](https://boards.straightdope.com/u/Shagnasty)\ **Post date:** [May 7, 2006, 1:12am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/4 "2006-05-07T01:12:58Z")
A very simple method is to label each of the five things with different outcomes of three coin flips. HHT TTH HTH THT TTT for example. It is like a lottery but there are only 8 possible outcomes and 5 “tickets”. Flip the coin in groups of three until one wins. There is a probability that none will win for many trials but the probability becomes mannishly small very fast. ---
**Author:** ![Shagnasty](https://avatars.discourse-cdn.com/v4/letter/s/9dc877/32.png) [@Shagnasty](https://boards.straightdope.com/u/Shagnasty)\ **Post date:** [May 7, 2006, 1:14am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/5 "2006-05-07T01:14:12Z")
A very simple method is to label each of the five things with different outcomes of three coin flips. HHT TTH HTH THT TTT for example. It is like a lottery but there are only 8 possible outcomes and 5 “tickets”. Flip the coin in groups of three until one wins. There is a probability that none will win for many trials but the probability becomes very small very fast. ---
**Author:** ![Race\_Bannon](https://avatars.discourse-cdn.com/v4/letter/r/5f8ce5/32.png) [@Race\_Bannon](https://boards.straightdope.com/u/Race_Bannon)\ **Post date:** [May 7, 2006, 1:15am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/6 "2006-05-07T01:15:23Z")
You could express your five choices as binary numbers: 000, 001, 010, 011, 100. Then you could flip the coin three times, assigning, say, heads =1, tails=0. Then if you get TTT, you pick the first. TTH, the second… HTT means the last. Now, since three binary digits can give 8 possible outcomes, you have to ignore the times when you get HTH, HHT, or HHH. If that happens, you just flip again three times. ---
**Author:** ![Frylock](https://avatars.discourse-cdn.com/v4/letter/f/ce7236/32.png) [@Frylock](https://boards.straightdope.com/u/Frylock)\ **Post date:** [May 7, 2006, 1:16am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/7 "2006-05-07T01:16:39Z")
Leave it to me to encomplicatify that which is in actuality quite unencomplicateficatory. Thanks guys! -FrL- ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [May 7, 2006, 1:20am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/8 "2006-05-07T01:20:42Z")
As I understand it, the fact that there’s no solution that doesn’t have a possibility of infinite coin flips required to reach a decision boils down to the fact that 1/5 is not a terminating binary fraction. You’d reach the same kind of issues, I think, trying to decide from three options, having only a ten-sided die. The moral - always try to have as large a number of possible different randomizers on hand as possible. 😃 ---
**Author:** ![elfbabe](https://avatars.discourse-cdn.com/v4/letter/e/b782af/32.png) [@elfbabe](https://boards.straightdope.com/u/elfbabe)\ **Post date:** [May 7, 2006, 1:24am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/9 "2006-05-07T01:24:50Z")
Oh, and in case you’re wondering, while **zut** ’s method is quite good at cutting down on the chance that you’ll have to do it over, you still can’t entirely eliminate that risk in this way. (why? Because no multiple of 5 is also a power of 2 - powers of two always end in the digits 2, 4, 8, or 6.) ---
**Author:** ![elfbabe](https://avatars.discourse-cdn.com/v4/letter/e/b782af/32.png) [@elfbabe](https://boards.straightdope.com/u/elfbabe)\ **Post date:** [May 7, 2006, 1:28am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/10 "2006-05-07T01:28:28Z")
> [@chrisk](#): > > The moral - always try to have as large a number of possible different randomizers on hand as possible. 😃 Geek → English translation: I need to buy more of those pretty, shiny polyhedral dice. … Not that I’d know anything about that. 😉 ---
**Author:** ![Excalibre](https://avatars.discourse-cdn.com/v4/letter/e/898d66/32.png) [@Excalibre](https://boards.straightdope.com/u/Excalibre)\ **Post date:** [May 7, 2006, 6:39am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/11 "2006-05-07T06:39:20Z")
> [@elfbabe](#): > > Geek → English translation: I need to buy more of those pretty, shiny polyhedral dice. > … Not that I’d know anything about that. 😉 Or carry around coins with more than two sides. I can’t help it if your pitiful HU-MON universe is only three-dimensional. ---
**Author:** ![don\_t\_ask](https://avatars.discourse-cdn.com/v4/letter/d/e68b1a/32.png) [@don\_t\_ask](https://boards.straightdope.com/u/don_t_ask)\ **Post date:** [May 7, 2006, 9:25am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/12 "2006-05-07T09:25:30Z")
Toss the coin once for each option. If you get 5 heads or 5 tails - no decision. 4 heads/tails and 1 of the other it is the selected option. 3 heads/tails and 2 of the other just a simple “heads you win…” ---
**Author:** ![gabriela](https://avatars.discourse-cdn.com/v4/letter/g/db5fbb/32.png) [@gabriela](https://boards.straightdope.com/u/gabriela)\ **Post date:** [May 7, 2006, 10:27am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/13 "2006-05-07T10:27:14Z")
I really like Elfbabe’s reply. ---
**Author:** ![gabriela](https://avatars.discourse-cdn.com/v4/letter/g/db5fbb/32.png) [@gabriela](https://boards.straightdope.com/u/gabriela)\ **Post date:** [May 7, 2006, 10:28am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/14 "2006-05-07T10:28:30Z")
Replies. (pretty polyhedrons) ---
**Author:** ![RTFirefly](https://avatars.discourse-cdn.com/v4/letter/r/c77e96/32.png) [@RTFirefly](https://boards.straightdope.com/u/RTFirefly)\ **Post date:** [May 7, 2006, 11:01am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/15 "2006-05-07T11:01:40Z")
> [@elfbabe](#): > > Geek -\> English translation: I need to buy more of those pretty, shiny polyhedral dice. Do they make icosahedral dice? That would be perfect for those 5-way decisions. 🙂 ---
**Author:** ![glee](https://avatars.discourse-cdn.com/v4/letter/g/b5a626/32.png) [@glee](https://boards.straightdope.com/u/glee)\ **Post date:** [May 7, 2006, 11:07am UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/16 "2006-05-07T11:07:02Z")
> [@RTFirefly](#): > > Do they make icosahedral dice? That would be perfect for those 5-way decisions. 🙂 I have bought 4, 6, 8, 12 and 20 sided dice. I have seen a 30 and a 100 sided die advertised. So the guaranteed one-off solution is to use the coin to buy a d20 (and allocate 4 numbers to each choice). 🙂 ---
**Author:** ![chrisk](https://avatars.discourse-cdn.com/v4/letter/c/6de8d8/32.png) [@chrisk](https://boards.straightdope.com/u/chrisk)\ **Post date:** [May 7, 2006, 12:05pm UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/17 "2006-05-07T12:05:14Z")
> [@glee](#): > > I have bought 4, 6, 8, 12 and 20 sided dice. > > I have seen a 30 and a 100 sided die advertised. > > So the guaranteed one-off solution is to use the coin to buy a d20 (and allocate 4 numbers to each choice). 🙂 Which would seem to indicate that the smallest number of solutions for which no pre-existing dice we know of would work evenly is… seven. Hmm… Would it be possible to make a decent 14-sided die as a spindle, like the [Ten-sided die](http://en.wikipedia.org/wiki/Ten-sided_die) 😃 ---
**Author:** ![BobLibDem](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/boblibdem/32/3149_2.png) [@BobLibDem](https://boards.straightdope.com/u/BobLibDem)\ **Post date:** [May 7, 2006, 12:49pm UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/18 "2006-05-07T12:49:48Z")
I would do this. Call the choices A thru E. I would flip one coin to determine A’s fate. If heads, A moves on. If tails, A is eliminated. Do the same for B-E. If all five are elimnated or all five move on, repeat. Otherwise, you get this: If four are left, make a tournament bracket for the survivors, single elimination. If three are left (say 1, 2, and 3) do a flip-off 1v2, 2v3, and 1v3. The choice that is 2-0 wins. If two are left, then flip to see which wins. If one is left, then you’re done. ---
**Author:** ![zut](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/zut/32/2875_2.png) [@zut](https://boards.straightdope.com/u/zut)\ **Post date:** [May 7, 2006, 12:54pm UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/19 "2006-05-07T12:54:31Z")
> [@elfbabe](#): > > Oh, and in case you’re wondering, while **zut** ’s method is quite good at cutting down on the chance that you’ll have to do it over, you still can’t entirely eliminate that risk in this way. (why? Because no multiple of 5 is also a power of 2 - powers of two always end in the digits 2, 4, 8, or 6.) If I’ve done my math correctly (which admittedly, I may not have), with the three coin method, you would expect to flip 4.8 coins total. With four, you would expect to flip 4.2667 coins total. You could do the same procedure with more coins, but you’d clearly get an even larger expected number of flips, so four seems optimum. ---
**Author:** ![kanicbird](https://avatars.discourse-cdn.com/v4/letter/k/5f8ce5/32.png) [@kanicbird](https://boards.straightdope.com/u/kanicbird)\ **Post date:** [May 7, 2006, 2:09pm UTC](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714/20 "2006-05-07T14:09:48Z")
Flip the coin once for each object, tails it’s out, head’s it’s still in. Repeat till one object is left or a easier way of flipping comes up (i.e. if 3 were out, and only 2 were still in after the first flipping, you could do heads for one tails of the other) It may take more flips, but it is easy to do and no complex flipping plans developed ahead of time. [Next page](https://boards.straightdope.com/t/selecting-randomly-from-five-options-using-only-a-coin/355714.md?page=2)