Choosing Four Numbers from 1..9 Using Seven Coin Flips

Nov/15/2009

There are 126 ways to choose four items from a set of 9, and there are 128 results from flipping a two-sided coin seven times. The procedure below lets you make a random choice of four numbers from nine using seven flips of a coin. The procedure will succeed about 98% of the time. The rest of the time it will fail, requiring you to start over.

Before we start, we divide the numbers into four pairs, {1,5}, {2,6}, {3,7}, and {4,8}, with 9 leftover as a special case. 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.

If 9 is not one of the chosen numbers, the four 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”). If 9 is one of the chosen numbers, the other three numbers either fall into three different pairs (“9-111”), or two will fall into one pair and one into another (“9-21”). The procedure will use three or four flips to decide between these cases, and also to decide which pairs are non-empty. The final three or four flips then finish off the selection.

   

The procedure:
  1. Flip three coins and place them, in the order they are flipped, on the numbers 1, 2 and 3.
  2. [“1111” case] If there are no heads, we will use one number from each of the four pairs.
    1. Pick up the three coins.
    2. Consider the four pairs from left to right. For each of four flips, if it is heads, place a coin to the higher number in the pair. Otherwise, place one on the lower number.
    3. The procedure is finished. The four coins mark the chosen numbers.
  3. [“211” case] If there is only one head, we will use three of the pairs, with the head being used (indirectly) to indicate which pair to double up.
    1. Make a note of whether the head is on 1, 2 or 3. Call this value “X”.
    2. Place a coin on 4 (1..4 all have coins)
    3. Flip two coins to determine which of the four pairs will be empty. Interpreting them in binary, remove the coin from the indicated pair.
    4. Considering the three chosen pairs left to right, place a coin on the higher number of the “X”th pair.
    5. Consider the two remaining 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.
    6. The procedure is finished. The four coins mark the chosen numbers.
  4. Flip a coin and place it on 4.
  5. [“9-21” case] If there are only two heads, 9 is chosen, and we will use two of the pairs.
    1. There is one tail among 1, 2 or 3. Make a note of which it is. Call this value “X”.
    2. Pick up the four coins.
    3. Flip two coins to determine which of the four pairs will be have both numbers chosen. Interpreting them in binary, place coins on both the lower and higher numbers of the the indicated pair.
    4. Considering the three empty pairs left to right, flip a coin and place it on the “X”th pair; if it is heads, place it on the higher number, otherwise on the lower.
    5. Place a coin on 9.
    6. The procedure is finished. The four coins mark the chosen numbers.
  6. [“9-111” case] If there are three heads, 9 is chosen, and we will use three of the pairs.
    1. The three heads mark the chosen pairs. Remove the tail.
    2. 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.
    3. Place a coin on 9.
    4. The procedure is finished. The four coins mark the chosen numbers.
  7. [“22” case] Otherwise, there are four heads.
    1. Pick up the four coins.
    2. Flip three coins and place them, in the order they are flipped, on the numbers 1, 2 and 3.
      1. If all four are the same, pick them up and start over at (A).
    3. Pick up all the tails.
    4. If only one coin is placed, place a coin on number four. After this step, two coins will have been placed.
    5. Place coins on the higher number for each of the two chosen pairs.
    6. The procedure is finished. The four coins mark the chosen numbers.
Back to Bob’s main Dice and Coins page.