The Clock Game:

An Introduction to the Vocabulary of Dynamics

Bob Gregory

Introduction

One of the ideas often developed in elementary school is the idea of converting base 10 numbers to base 2 numbers (often called binary numbers). This idea is easily accessible to students using a clock-like manipulative. Here we will use the idea of converting bases to introduce the vocabulary of dynamic systems and to develop the idea in students that math is an experimental science. Other concepts used here which can also be developed or ignored depending on the level of the students are composition of functions, summing geometric series, and modular arithmetic.

Conversion of Whole Numbers to Base 2

The idea of converting whole numbers to base 2 is usually accomplished by talking about place value. Assuming the students already know 13 (base 10) is 1 ten and 3 ones. In base 2 the digits represent powers of 2. The base 2 (binary) number 1101 is equivalent to 13 (base 10). Examine the table to see

eights fours twos ones

1 1 0 1

From the above table we see 1*(8) + 1*(4)+ 0*(2) +1*(1) = 13.... The value of the digits is always a 0 or a 1 in base 2 arithmetic.

Exercise: Express the binary (base 2) number 10001 as a base 10 number. (answer 17)

Question: How would you convert 19 to a binary number ? To convert 19 to binary, first find the largest power of 2 less than or equal to 19. 16 is this number so 19 = 1*(16) + something. To find the rest subtract 19 - 16 = 3, now find the largest power of 2 less than or equal to 3. 2 is the number so 19 = 1*(16) + 0*(8) + 0*(4) + 1*(2) + 1*(1) this means the binary representation of 19 is 10011. Remember the computer does its arithmetic in binary (base 2) numbers.

Exercises:

1) Convert the following base 10 numbers to base 2(binary), 3,7,14,29.

2) Convert the following base 2 numbers to base 10, 1100,10101,11001,1001

The Clock Game or Modular Arithmetic

The clock game helps students understand modular arithmetic. Start with a regular clock, but replace the 12 with a zero and use only one hand. You are now ready for mod 12 arithmetic. Let's add mod 12, start at the number four on the clock and add five. This is an easy exercise, so you should count five around the clock and get to the number nine. We say 4+5 = 9 (mod 12). If we add five to the result, move five around the clock and end up at two. We say 9+5 = 2 (mod 12). If a student can tell time this should be no surprise, since five hours after nine o'clock is two o'clock. Essentially the number two in mod 12 arithmetic is equivalent to the number fourteen. What are some other numbers equivalent to the number two? The number two is equivalent mod 12 to 2 12*n (where n is any integer). Take some time and play by adding different values and examine the results.

The next step is to try to figure out subtraction. In the usual way we can start off saying "what do I add to nine to get two?" The students should soon see 2-5 = 9 (mod 12). Visually you can verify this result by pointing the arrow at two and counting back five. Without the visual aid think of 2 (mod 12) as 14 and then subtract 5 to get 9.

Next we want to examine the iteration game using the clock. Let's examine the process of adding 4 (mod 12); we get very different results depending on the number we start with. The number we start with will be called the seed. Let's use a seed of one and see what happens when we use the iterative process of adding 4 (mod 12). This process is a function. Take some time and experiment with different processes and use different moduli.

The list of numbers generated by the iterative process of adding 4 (mod 12) to 1 is called the orbit of 1. The orbit of 1 under the process of adding 4 (mod 12) is 1,5,9,1,5,9,1,5,9... Since this process yields a sequence of numbers which repeats every third element, we can determine the value at any point in the process. What will the 50th point in the orbit be? When a sequence is generated that repeats in a cycle like ours we call the orbit a 3-cycle or a cycle of period 3. We also say the orbit has period 3. Try using 6 as a seed and repeat this process to find the orbit of 6. Can you find a seed which gives a 2-cycle under this process? (Actually no.) See if the students can develop a process which gives a 2-cycle, a 4-cycle and a 7-cycle. Under mod 12 addition and subtraction only cycles of period 1, 2, 3, 4, 6, and 12 are possible. Notice finding the orbit of this function is done using composition of functions. f(1) = 4, f(f(1)) = 9, f(f(f(1))) = 1...we use the notation . We also say . Below is an orbit diagram; the arrows tell where the orbit goes after one iteration.

How can we change the game to get different cycles? Let's change our clock to a modulo 10 clock. Look at the process of subtracting 2 and use a seed of 7. The orbit of 7 is 7,5,3,1,9,7,5,... notice once the numbers start to repeat you can stop iterating because you know the rest of the orbit (why?). The orbit of 7 is a 5-cycle under this process of mod 10 subtraction.

The Doubling Process (Function)

The doubling process is just as it sounds: you double the number and convert the answer into the appropriate base. Let's do the doubling process on 5 in mod 7. First we double 5 to get 10, then convert 10 (mod 7) giving an answer of 3. The doubling of 5 using mod 7 is 3. What is the double of 1 (mod 12)? What happens if we iterate the doubling process? Under the doubling process (mod 12) the orbit of 1 is 1, 2, 4, 8, 4, 8, 4, 8,.... Notice the orbit of 1 eventually is a cycle of period 2 (2-cycle). We call 1 a pre-periodic point because its orbit is eventually periodic. Let's examine the orbit of 4 (mod 5) under the doubling process. The orbit of 4 (mod 5) is 4, 3, 1, 2, 4, 3, 1, 2,... a 4-cycle (cycle of period 4).

Binary Decimals

Next examine the conversion of fractions to binary decimals. 1/2 has a binary representation .1, 1/4 has a binary representation of .01, 1/8 has a binary representation of .001 and so on. Lets express 1/3 as a binary decimal, 1/3 is less than 1/2 in much the same manner as we did with whole numbers.

1/3 = 0*(1/2) + 1*(1/4) + 0*(1/8) + 1*(1/16) + 0*(1/32) + 1*(1/64) + ...

so 1/3 = . We can check by summing the infinite geometric series above.

1/4 + 1/8 + 1/64 + ... = 1/3

Try converting 4/5 to a binary decimal

4/5 = 1*(1/2) + 1*(1/4) + 0*(1/8) + 0*(1/16) + 1*(1/32) + 1*(1/64) + ...

4/5 = we can verify this answer by adding two infinite geometric series

1/2 + 1/32 +1/512 +... = 8/15 and 1/4 + 1/128 + 1/1024 +... = 4/15 to get 4/5. So it checks. Most students (and some teachers) don't have the patience for this process so let's look at a shortcut. We will need the doubling process (function). To compute 4/5 we need to find the orbit of 4 (mod 5) under doubling. We have seen this orbit to be 4,3,1,2,... now divide the base in half. 5 is the base so the low half is 0,1,2 and the high 1/2 is 3,4. To compute the binary representation of 4/5 look at its orbit if the number in the low half the decimal place gets a 0, if the number is in the high half the decimal place gets a 1. The orbit of 4 (base 5) is high, high, low, low,... so the binary decimal for 4/5 = Try to verify 1/5 = .

Another Neat Trick

Another way to find the binary expression of 7 base ten number is to first determine the smallest power of 2 larger than 7. Then play the doubling game using 7 as a seed and base 8. The orbit of 7 is 7, 6, 4, 0. Now look at these number as high and low as before to see our orbit is high, high, high so 7 = 111. Try to express 13 as a binary number. Remember we now play the doubling game base 16. The orbit of 13 is 13,10,4,8,0 so we have high, high, low, high this means 13 = 1101.

Summary

The doubling process is adapted from a talk by Robert Devaney of Boston University. Remember the idea of math as an experimental science. Consider the relationship between mod 3 and a tripling function. The same ideas can be developed. Encourage the students to try different things and conjecture about possible outcomes.

Woodrow Wilson Leadership Program in Mathematics

lpt@www.woodrow.org
The Woodrow Wilson National Fellowship Foundation

webmaster@woodrow.org
CN 5281, Princeton NJ 08543-5281

Tel:(609)452-7007

Fax:(609)452-0066