Choosing Three Numbers from 1..12 Using Eight Coin Flips

Nov/15/2009

There are 220 ways to choose three items from a set of 12, and there are 256 results from flipping a two-sided coin eight times. The procedure below lets you make a random choice of three numbers from twelve using eight flips of a coin. The procedure will succeed about 86% of the time. The rest of the time it will fail, requiring you to start over.

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 three chosen numbers either fall into three different pairs (we’ll call this “111”) or two will fall into one pair and one into another (“21”). The procedure will use five flips to decide between these cases, and also to decide which pairs are non-empty. The final three 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.
  2. If there are more than three heads, pick them up. Otherwise, pick up all the tails.
    1. Set one of the picked-up coins aside, keeing it as heads or tails. This “rescued” flip may be used in step (E.6).
  3. If the number of placed coins is even, place a coin on number 6. After this step, there will either be three coins placed or just one.
  4. [“111” case] If there are three coins placed, they mark the three 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 three 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 three coins mark the chosen numbers.
  5. [“21” case] Otherwise, there is only one coin placed. It marks a chosen pair; we will use both the numbers from this pair, and one of the other numbers. Steps (E.2) through (E.4) use three flips, plus the flip rescued from (B.1) to select one of the ten remaining numbers.
    1. Place a coin on the higher number of the chosen pair (both numbers in the pair are marked).
    2. Flip three coins and place them, in the order they are flipped, below the numbers 1, 2 and 3.
      1. If they are all the same, start over at step (A).
    3. Of the three coins, two are the same; remove them.
    4. If the remaining coin is a head, move it three spots to the right (i.e. add 3).
    5. If the remaining coin is in the same column as the chosen pair, start over at step (A).
    6. If the coin rescued from (B.1) is heads, move the remaining coin to the higher number in its pair. Otherwise, move it to the lower number.
    7. The procedure is finished. The three coins mark the chosen numbers.
Back to Bob’s main Dice and Coins page.