Unit: Fibonacci Nim
In early grades, students learn that a decimal integer is a sum of
multiples of integer powers of 10. In this lesson, students are asked
to interpret a numeral given in a base other than 10 as a sum of
multiples of powers of that base, b. Finally, students learn to use two methods for writing a given decimal integer in base b.
Begin by reminding students what place value means, using an example.
For example, the place value interpretation of 4273 is 4000 + 200 +
70 + 3, which is a sum of multiples of powers of 10. Note that 4000 =
4(103) is a multiple of a power of 10. Similarly, 2(102), 7(101), and 3(100) are multiples of powers of 10, too.
For students familiar with algebra tiles, the following diagram shows a physical representation of 4273.
When a number is expressed in a base other than b, the interpretation is similar. For convenience, assume that b = 6. The procedures outlined below will work no matter what the value of b is, but fixing the value of b makes the discussion much easier.
Next, show that base‑6 numerals can be interpreted in the same way as base 10 numerals. The notation 21136
is interpreted as a sum of multiples of powers of 6, just as 4273 was
interpreted as a sum of multiples of powers of 10 above. The
subscript 6 must be attached unless we are using base 10, because 10 is
the default value of the base, by convention. Thus, 21136 = 2(63) + 1(62) + 1(61) + 3(60) = 477. Thus, 21136
is interpreted as 477. The reverse process—that of finding the base‑6
representation of an integer expressed in decimal notation—is harder
but more interesting. There are two methods for completing such a
conversion: (a) repeated subtraction and (b) repeated division. Each method has some advantages over the other.
Lead students through the processes of repeated subtraction and
repeated division for converting the decimal number 477 to base‑6.
Make a list of all the (positive) integer powers of 6 that are less
than the given number. For 477, the following powers are needed: 60 = 1, 61 = 6, 62 = 36, and 63 = 216. (Note that the next power of 6, 64 = 1296, is greater than 477.)
Next, as the name implies, repeatedly subtract the largest power of 6 that is less than or equal to the current number
(which changes during the process). Performing the first subtraction,
the amount remaining is 477 – 216 = 261. At this point, the current
number is 261; because it is still larger than 63 = 216, repeat the process. Then, 477 – 2(216) = 45, so the current number becomes 45.
Now, because the current number is less than 63 = 216 but greater than 62 =
36, repeatedly subtract 36. This gives 45 – 36 = 9. Putting this
together with the above result gives 477 = 2(216) + 1(36) + 9. As a sum
of multiples of powers of 6, the remaining current number, 9, leads to
9 = 1(6) + 3(1).
Combining all of this work gives 477 = 2(63) + 1(62) + 1(61) + 3(60) = 21136. (This result agrees with the result above.)
At this point, ask each student to pick a three‑digit decimal number.
Then ask them to use repeated subtraction to find its base‑6
representation. Finally, they should expand their numeral to get back
the original three‑digit decimal number. An alternative approach would
be to have students work in pairs to find the base‑6 representation.
Once they have the representation completed, they can exchange their
answer with another pair of students and interpret the base‑6 numeral
they receive back into its original three‑digit decimal representation.
Repeated subtraction has two advantages over the method of repeated
division. First, it is closely related to the definition, hence it
leads to a better conceptualization. Second, it can be used in other
situations when repeated division cannot, as in the case of Fibonacci
representation (explained below).
The process of repeated division requires continual division by the base, b, and interpreting the results.
When 4273 is divided by 10, the remainder is 3, which is the units
digit of 4273. The integer quotient of that division is 427; and if 427
is then divided by 10, the remainder is 7, which is the tens digit
In the same way, repeated division enables an integer to be expressed as the sum of multiples of powers of b, where b is an integer. In fact, the process even works when b is negative.
Using the repeated division algorithm for our example above, first
divide 477 by 6. This gives a quotient of 79 with a remainder of 3. In
other words, 477 = 6(79) + 3. (Notice that the remainder can never
exceed 5, since in such a case the quotient would have been larger.)
Next, divide the quotient by 6, and record the new quotient and
remainder. Thus, 79 = 6(13) + 1. Repeat the process: 13 = 6(2) + 1, and
finally 2 = 6(0) + 2. Writing the remainders in reverse order gives the
base‑6 representation of 21136.
To further illustrate the process, consider the following example.
To see why 477 = 21136, repeatedly replace each quotient with its value obtained during the division process. Consequently,
The advantage of repeated division over repeated subtraction is that it
is computationally more efficient. Also, the method of justification
can be applied in other situations, such as synthetic division and the
At this point, ask each student to pick a three‑digit number. Then ask
them to use repeated division to find the base‑6 representation.
Finally, they should expand their numeral to get back the original
three‑digit decimal number. An alternative approach would be to have
students work in pairs to find the base‑6 representation. Once they
have the representation completed, they can exchange their answer with
another pair of students and interpret the base‑6 numeral they receive
back into its original three‑digit decimal representation.
The following applet can be used to convert between bases. In the
classroom, you can display this applet and use it to verify student
Alternatively, the following program for the TI-83+ graphing calculator will convert any number from base‑10 to base b, where 2 ≤ b ≤ 9.
The program can be downloaded to student calculators, or you can
download it to a calculator with projection capabilities and display
the results on the overhead projector.
TI-83+ Base Converter
Next ask the students to complete the Binary Representations Activity Sheet.
Binary Representations Activity Sheet
This page contains all the binary
representations of the numbers 0 through 31 and can be completed
individually, although allowing students to work in groups will reduce
errors as well as decrease the time required for completion. Ask
students to compare the left and right sides of the page for
similarities. Consider the pattern of 0’s and 1’s in each column.
Students may notice the following:
Binary Representations Answer Key
To see these patterns, you may wish to view the solutions
to the activity sheet.
At this point students should be able to complete the Place Value Activity Sheet questions 1‑4. Challenge questions are also available at the end of the activity sheet.
Place Value Activity Sheet
Note: Prior to beginning the lesson, you may wish to review the solutions.
Place Value Answer Key
Just as every positive integer
can be expressed as a sum of distinct powers of 2, 6, or 10, every
integer can also be expressed as a sum of Fibonacci numbers.
Although this can be done in several ways, the method for this lesson is known as a greedy algorithm. It’s called "greedy" because at each stage, the largest possible number is chosen.
This method is based on the method of repeated subtraction. To represent a number N, pick the largest Fibonacci number not exceeding N, then subtract it and continue with the difference. For example, consider N = 100.
The largest Fibonacci number less than 100 is 89, so subtract 89. The
result is 100 – 89 = 11. Because 11 is less than the Fibonacci
numbers 55, 34, 21, and 13, they cannot be subtracted. The next
Fibonacci number that can be subtracted is 8, and 11 – 8 = 3. Because 3
is a Fibonacci number, the subtraction is complete.
To interpret the results, write the original number as a sum of Fibonacci numbers:
Practice this with your students by asking them to convert back and
forth, making sure that you get back the number with which you started.
In addition, counting in Fibonacci is something all students
should eventually be able to do: 1, 10, 100, 101, 1000, 1001, 1010,
10000, …. (Note that counting in Fibonacci numbers is the next-to-last
question on the activity sheet.) Students should also think about why
Fibonacci representations never have two consecutive 1’s, no matter
what integer is represented.
In another lesson in this unit, the Fibonacci representation is used to
provide a strategy for playing a variation of the game Nim.
Questions for Students
1. If you wish to convert a number, n, from base 10 to base b by the repeated subtraction method, the first p powers of b are needed. Write an inequality involving n, b and p that can be used to identify the maximum value of p that will be needed.
[If bp < n < bp + 1, then the maximum power of b that is needed for the repeated subtraction method is p.]
2. When using the repeated division algorithm, why can't the remainder exceed the divisor d?
[If the remainder was larger than the divisor, it means the quotient was not corect and that more groups of size d can be removed from the dividend.]
3. What advantage does repeated division have over repeated subtraction for converting a number to another base?
[Repeated division is computationally more efficient.]
4. Why will a Fibonacci representation never contain two consecutive 1’s?
[The nature of the Fibonacci pattern is that each number is equal to the
sum of the two previous numbers. Consequently, two consecutive 1’s
should be replaced by 0’s, and the next larger place value should
increase by 1. For instance, the incorrect Fibonacci representation 110
can be interpreted as the decimal sum 3 + 2 + 0 = 5; but since 5 is a
Fibonacci number, this should instead be represented as 1000.]
6th to 8th
9th to 12th
Grade: High School
Represent numbers in other bases and convert to and from decimal representations, and then, learn how to play Static Nim.