Binary Notation Card Trick

Date: 12/10/2002 at 20:10:11
From: Jonathon
Subject: Card Game

My 7th grade teacher had a card game that had about 7 cards. She said 
she could guess your number by asking you if your number was on each 
card. Can you teach me how to play this game. All I remember is that 
one card had even numbers and the other had odd.

Date: 12/11/2002 at 13:04:08
From: Doctor Ian
Subject: Re: Card Game

Hi Jonathan,

I think I know the game you're talking about. I have a friend who 
pulls this all the time on unsuspecting children. To understand it, 
you have to know how binary ('base 2') notation works.

Consider a number like 423.  This is a shorthand representation for 

  4*100 + 2*10 + 3*1

That is, the value contributed by each digit is the digit times a
power of 10:

  10^2  10^1  10^0
  ----  ----  ----
    4     2     3     = 4*100 + 2*10 + 3*1
    3     0     9     = 3*100 + 0*10 + 9*1

and so on.  This, by the way, is what makes zero so valuable. 

Instead of using all 10 digits in base 10, we can do the same sort of 
thing using only 2 digits (0 and 1), in base 2:

   2^3   2^2   2^1   2^0
   ---   ---   ---   ---
    0     0     0     1   = 0*8 + 0*4 + 0*2 + 1*1 = 1
    0     0     1     0   =             1*2       = 2
    0     0     1     1   =             1*2 + 1*1 = 3
    0     1     0     0   =       1*4             = 4
    0     1     0     1   =       1*4       + 1*1 = 5
    0     1     1     0   =       1*4 + 1*2       = 6
    0     1     1     1   =       1*4 + 1*2 + 1*1 = 7
    1     0     0     0   = 1*8                   = 8

and so on. Here are the binary representations of the numbers from 1
to 15:

  base 10    binary
  -------    -------
        1    0 0 0 1  
        2    0 0 1 0 
        3    0 0 1 1
        4    0 1 0 0
        5    0 1 0 1
        6    0 1 1 0 
        7    0 1 1 1
        8    1 0 0 0
        9    1 0 0 1
       10    1 0 1 0
       11    1 0 1 1
       12    1 1 0 0
       13    1 1 0 1
       14    1 1 1 0 
       15    1 1 1 1

Now we're ready to make our cards. To make the first card, we choose
every number that has a '1' in the rightmost column:

   1  3  5  7 
   9 11 13 15

To make our second card, we choose every number that has a '1' in the
next column over (i.e., the second column from the right):

   2  3  6  7
  10 11 14 15

We make the next two cards the same way:

   4  5  6  7
  12 13 14 15

and
   
   8  9 10 11
  12 13 14 15

So here are our cards:

     Card 4          Card 3         Card 2         Card 1
  +-----------+  +-----------+  +-----------+  +-----------+ 
  | 8  9 10 11|  | 4  5  6  7|  | 2  3  6  7|  | 1  3  5  7|
  |12 13 14 15|  |12 13 14 15|  |10 11 14 15|  | 9 11 13 15|
  +-----------+  +-----------+  +-----------+  +-----------+

Now, let's pick a number at random, like 12. Which cards does it 
appear on? Cards 3 and 4. Let's add the first numbers that appear on
those cards: 4 + 8 = 12. How about that!

Let's try another number, like 7. It appears on cards 1, 2, and 3, so
we'll add the first numbers from those cards: 1 + 2 + 4 = 7.

Do you see what's going on?  By telling you what cards a number 
appears on, I'm telling you the digits that appear in its binary
representation.  

In other words, if the number 12 appears on cards 3 and 4, then its
binary representation must be 1100. If the number 7 appears on cards
1, 2, and 3, its binary representation is 0111.  And so on. 

And what is the first number on each card?  It's the power of 2 that
corresponds to the column we used to make the card!  

So, doing this:

   Choose a number from these cards.  Find the cards that
   it appears on, and add the first numbers from those cards.
   The sum will be equal to the number you chose. 

   +-----------+  +-----------+  +-----------+  +-----------+ 
   | 8  9 10 11|  | 4  5  6  7|  | 2  3  6  7|  | 1  3  5  7|
   |12 13 14 15|  |12 13 14 15|  |10 11 14 15|  | 9 11 13 15|
   +-----------+  +-----------+  +-----------+  +-----------+

is _exactly_ the same as doing this:

   Choose a number from the following list.  Find the columns
   next to it that contain a '1', and add the numbers at the
   tops of those columns.  The sum will be equal to the number
   you chose. 

              8 4 2 1
              -------
         1    0 0 0 1  
         2    0 0 1 0 
         3    0 0 1 1
         4    0 1 0 0
         5    0 1 0 1
         6    0 1 1 0 
         7    0 1 1 1
         8    1 0 0 0
         9    1 0 0 1
        10    1 0 1 0
        11    1 0 1 1
        12    1 1 0 0
        13    1 1 0 1
        14    1 1 1 0 
        15    1 1 1 1

When you add the first numbers of the cards on which a number appears,
you're just adding up the binary representation of the number. 

You can do this with more numbers, of course. Adding one more card 
(one more column) will give you the numbers from 1 to 31; adding two
columns will give you the numbers from 1 to 63; and so on. With N 
cards, you can use the numbers from 1 to (2^N-1).  

But it's just more numbers.  The trick is exactly the same.

Does this make sense? 

- Doctor Ian, The Math Forum
  http://mathforum.org/dr.math/