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. I’ve replaced the die with coin flips. The procedure below is different than Wei-Hwa’s. 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 (we’ll 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:
  1. Flip five coins and place them, in the order they are flipped, on the numbers 1, 2, 3, 4 and 5.
    1. If all five are heads, pick them up and start over.
  2. Pick up all the tails.
  3. If there are exactly three coins, place a coin on number 6.
  4. [“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.
    1. 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.
    2. The procedure is finished. The four coins mark the chosen numbers.
  5. [“22” case] If there are no coins placed, this indicates that we have two complete pairs, as yet unchosen.
    1. Use four flips to determine two numbers in 1..6. If that procedure requires us to start over, start over back at step (A).
    2. Place coins on those two numbers, and also on the higher number in each of their pairs.
    3. The procedure is finished. The four coins mark the chosen numbers.
  6. [“211” case] Otherwise, there are one or two coins placed.
    1. If only one coin is one coin is placed, we record “middle” as a state variable and continue at step (F.3).
    2. If two coins are placed, we will remove one as follows:
      1. Consider the distance between the two coins, which is either 1, 2, 3 or 4.
      2. 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).
      3. 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.
    3. 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”.
    4. 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.
    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.
    6. 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.
    7. 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.
    8. The procedure is finished. The four coins mark the chosen numbers.
Back to Bob’s main Dice and Coins page.