Choosing Four Numbers from 1..12 Using Nine Coin Flips
Nov/15/2009
There are 495 ways to choose four items from a set of 12, and there are 512
results from flipping a two-sided coin nine times. This small difference was
pointed out by Wei-Hwa Huang back in 2008, and he
posted a challenge
to find a simple-to-remember procedure that would let you make a random choice
of four numbers from twelve using three rolls of an eight-sided die. Ive
replaced the die with coin flips. The procedure below is different than
Wei-Hwas. It will succeed about 97% of the time. The rest of the time
it will fail, requiring you to start over (usually when this happens it is
after only five flips).
Before we start, we divide the numbers into six pairs, {1,7}, {2,8}, {3,9},
{4,10}, {5,11} and {6,12}. The procedure makes use of the diagram below, which
can be drawn on a scrap of paper. Coins are placed on the diagram to indicate
which numbers are chosen.
The four chosen numbers either fall into four different pairs (well
call this 1111), just two different pairs (22) or two will
fall into one pair and two into two others (211). The procedure will
use five flips to decide between these cases, and also to decide which pairs
are non-empty. The final four flips then finish off the selection.
The procedure:
- Flip five coins and place them, in the order they are flipped, on the
numbers 1, 2, 3, 4 and 5.
- If all five are heads, pick them up and start over.
- Pick up all the tails.
- If there are exactly three coins, place a coin on number 6.
- [1111 case] If there are four coins, including step (C) in the
count, they mark the four chosen pairs. We will use one of the numbers
from each of those pairs.
- Consider the chosen pairs from left to right. For each of four flips,
if it is heads, move the marker coin to the higher number in the pair.
Otherwise, leave it on the lower number.
- The procedure is finished. The four coins mark the chosen numbers.
- [22 case] If there are no coins placed, this indicates that we have
two complete pairs, as yet unchosen.
- Use four flips to determine two numbers in
1..6. If that procedure requires us to start over, start over back
at step (A).
- Place coins on those two numbers, and also on the higher number in each
of their pairs.
- The procedure is finished. The four coins mark the chosen numbers.
- [211 case] Otherwise, there are one or two coins placed.
- If only one coin is one coin is placed, we record middle as a
state variable and continue at step (F.3).
- If two coins are placed, we will remove one as follows:
- Consider the distance between the two coins, which is either 1, 2,
3 or 4.
- If the distance is 3 or 4, move the left coin five spots to the
right (i.e. add 5; a coin on 2 would move to an imaginary spot
to the right of 6).
- After (F.2.b), the distance is either 1 or 2. Record left
or right, respectively, as our state variable and remove the
rightmost coin.
- We now have exactly one coin placed, on a number 1..5, and a state
variable with one of three values. Call this coin X.
- Flip a coin (this is the 6th flip). If it is heads, place a coin on
X+1, wrapping around modulo 5. If it is tails, place a coin on X+2
(also wrapping). This leaves us with a random selection of two from
1..5.
- Flip a coin (this is the 7th flip). If it is heads, place a coin on 6.
If it is tails, place three coins on the empty spots in 1..5, and
remove the other two. This leaves us with a random selection of three
from 1..6, indicating three pairs.
- Our state variable now tells us which of the three pairs will have both
numbers marked. Left means that we mark the other half of the
leftmost pair, etc.
- Consider the two other chosen pairs from left to right. For each of
two flips, if it is heads, move the marker coin to the higher number in
the pair. Otherwise, leave it on the lower number.
- The procedure is finished. The four coins mark the chosen numbers.
Back to Bobs main Dice and Coins page.