A Base 2 Game

To play this game you have five sheets of paper, each of a different color. Each sheet contains numbers between 1 and 31. Ask someone to think of a number between 1 and 31 but not to tell you what is the number. Ask them to tell you on which sheets does their number appear. You can then tell them what is their number. How do we do this, and how can we build the game?

Here is the secret of how to determine somebody's number. Add the numbers in the top left corner of each sheet of paper on which the mystery number appears, and that will give you their number. For example, if, reading from left to right, a person's number appears on the first, second, and fourth sheets listed above, then their number is 1 + 2 + 4 = 7. We will see why this works and how to construct the sheets of paper in this assignment.

The key to this game is the binary, or base 2, representation of a number. As we saw in the assignment Base 2, every number can be written in base 2 as a series of 0's and 1's, and this represents writing a number a sum of powers of 2. For example,

19 = 16 + 2 + 1 = 10011 in base 2

and

28 = 16 + 8 + 4 = 11100 in base 2

Numbers from 1 to 31 can be written in base 2 with at most 5 symbols; that is, we need at most five place values to represent these numbers. Determining if a place is to have a 0 or a 1 corresponds to determining whether or not the corresponding power of 2 is needed to get the number. So, we need five pieces of information to determine the base 2 representation of a number between 1 and 31. You get five pieces of information when somebody tells you which sheets on which their number occurs; they have to answer yes it is on or no it is not on for each of the five pieces of paper.

To construct the game, first write each of the numbers from 1 to 31 as a sum of powers of 2. Next, on five sheets of paper of different colors, draw a large square and subdivide it into a 4 by 4 grid of squares. On the first page, place a 1 in the top left corner. Fill in the remaining squares with all of the numbers between 1 and 31 that have a 1 in the first (right most) digit of the base 2 representation of the number, or that need a 1 to write the number as a sum of powers of 2. On the next sheet of paper, place a 2 in the top left corner. Fill in the remaining squares with those numbers that have a 1 in the 2's place in the base 2 representation of the number, or that need a 2 to write the number as a sum of powers of 2. Do the same thing with the remaining three sheets of paper, placing 4, 8, and 16 in the top left corners, respectively. For instance, for the number 19, since 19 = 16 + 2 + 1, you would place 19 on the first, second, and fifth sheets, corresponding to 1, 2, and 16. Likewise, since 28 = 16 + 8 + 4, you would place 28 on the third, fourth, and fifth sheets, which correspond to 4, 8, 16. So, to determine the person's number, you add the numbers in the top left squares of each sheet on which their number appears.

You may place the numbers in any order on the sheets. However, the more systematic you place the numbers the easier it is for somebody to tell you on which sheets their number is located.

As practice in playing the game and doing arithmetic calculations in your head, working in pairs, have one person pick a number and the other person determine what is the number. Trade off so that each person gets a chance to determine the other person's numbers.

Problem. Describe how to guess a person's number from the information they give you. Next, write each whole number from 1 to 31 as a sum of powers of 2. Finally, describe how to use this information to build the five sheets; explain this by saying on which sheets the numbers 13 and 26 are to be placed upon.