This is part 2 of a discussion about Maile's solution to Challenge 03: Finger Counting. If you haven't explored that challenge or thought about her solution yet, please start here.
In her solution, Maile observes that the numeral 1000 can represent different numbers. It might represent one thousand. In fact, I think it's fair to say it "usually" represents one thousand because we usually interpret numerals in base 10. But, the symbol 1000 could just as easily represent eight if we interpret it in base 2. (In fact, it could just as easily represent a lot of numbers: sixty-four, four thousand ninety-six, negative twenty-seven... but let's not get ahead of ourselves.)
Maile answers the challenge by claiming that we can stop finger counting at eight rather than counting all the way to one thousand, since 1000 represents the number eight in base 2. She's right in that we do in fact land on the same finger. "But," I wondered, "Does that always work?"
(As a quick aside, I have to appreciate the lucky randomness of the fact that I chose 1000 as the target number. That is to say, if I had asked what finger we'd be on when counting to 500 or to 2000, the connection to binary numbers would never, I suspect, have come up.)
To answer the question "does it always work?", it's helpful to watch Paul's solution to the challenge, in which he makes the connection between this kind of finger counting and modular arithmetic. If a number is congruent to either 2 or 0 modulo 8 it will end up on your index finger. Since \(1000 \equiv 0 \mod{8}\), we end up on the index finger when we count to 1000.
Said the other way around: if two numbers are congruent modulo 8, then they will end up on the same finger when finger counting in this way. So here was the question I had:
In her solution, Maile observes that the numeral 1000 can represent different numbers. It might represent one thousand. In fact, I think it's fair to say it "usually" represents one thousand because we usually interpret numerals in base 10. But, the symbol 1000 could just as easily represent eight if we interpret it in base 2. (In fact, it could just as easily represent a lot of numbers: sixty-four, four thousand ninety-six, negative twenty-seven... but let's not get ahead of ourselves.)
Maile answers the challenge by claiming that we can stop finger counting at eight rather than counting all the way to one thousand, since 1000 represents the number eight in base 2. She's right in that we do in fact land on the same finger. "But," I wondered, "Does that always work?"
(As a quick aside, I have to appreciate the lucky randomness of the fact that I chose 1000 as the target number. That is to say, if I had asked what finger we'd be on when counting to 500 or to 2000, the connection to binary numbers would never, I suspect, have come up.)
To answer the question "does it always work?", it's helpful to watch Paul's solution to the challenge, in which he makes the connection between this kind of finger counting and modular arithmetic. If a number is congruent to either 2 or 0 modulo 8 it will end up on your index finger. Since \(1000 \equiv 0 \mod{8}\), we end up on the index finger when we count to 1000.
Said the other way around: if two numbers are congruent modulo 8, then they will end up on the same finger when finger counting in this way. So here was the question I had:
Given a numeral made up only of the digits 1 and 0, are the base 2 value of this numeral and the base 10 value of this numeral always congruent modulo 8?
This is a cool problem to solve, and you might want to kick this problem around before reading on. My gut feeling was that the answer was yes, but I needed to crack open a number theory book to prove it.
Two numbers are congruent modulo \(n\) if their difference is a multiple of \(n\). Given a ones-and-zeros numeral, we'd like to show that the difference between the decimal interpretation and the binary interpretation of that numeral is a multiple of 8.
Let's imagine an arbitrary string of 1s and 0s that is \(n\) symbols long. We might label the symbols \(b_{n-1} b_{n-2} \ldots b_2 b_1 b_0\), where each \(b_i\) is either 1 or 0.
When we interpret the string as a base 10 number, its value is \[b_{n-1} 10^{n-1} + \ldots + b_2 10^2 + b_1 10^1 + b_0 10^0.\]
On the other hand, when we interpret the string as a base 2 number, its value is \[b_{n-1} 2^{n-1} + \ldots + b_2 2^2 + b_1 2^1 + b_0 2^0.\]
Our goal is to show that the difference of these two is a multiple of eight. We subtract and gather up like terms, giving us \[b_{n-1} (10^{n-1} - 2^{n-1}) + \ldots + b_2 (10^2 - 2^2) + b_1 (10^1 - 2^1) + b_0 (10^0 - 2^0).\]
All of the terms have the same form: \(b_i (10^i - 2^i) = b_i 2^i (5^i - 1)\). When \(i \geq 3\) the term clearly has \(2^3 = 8\) as a factor. But what about the smaller terms, when \(i < 3\)? Well, we're in luck:
\begin{array}{l}
b_2(10^2 - 2^2) = b_2(96)\\
b_1(10^1 - 2^1) = b_1(8)\\
b_0(10^0 - 2^0) = b_0(0) \end{array}
Since each of the terms in the sum is a multiple of 8, the sum as a whole is a multiple of 8, which is what we wanted to show.
I think this is a great example of what makes teaching so challenging and exciting for me. I love being surprised by students and by the way they approach mathematics, and I love thinking deeply about so-called "simple" concepts.
I hope to hear from folks in the comments, either here or over at Math Mistakes!
Let's imagine an arbitrary string of 1s and 0s that is \(n\) symbols long. We might label the symbols \(b_{n-1} b_{n-2} \ldots b_2 b_1 b_0\), where each \(b_i\) is either 1 or 0.
When we interpret the string as a base 10 number, its value is \[b_{n-1} 10^{n-1} + \ldots + b_2 10^2 + b_1 10^1 + b_0 10^0.\]
On the other hand, when we interpret the string as a base 2 number, its value is \[b_{n-1} 2^{n-1} + \ldots + b_2 2^2 + b_1 2^1 + b_0 2^0.\]
Our goal is to show that the difference of these two is a multiple of eight. We subtract and gather up like terms, giving us \[b_{n-1} (10^{n-1} - 2^{n-1}) + \ldots + b_2 (10^2 - 2^2) + b_1 (10^1 - 2^1) + b_0 (10^0 - 2^0).\]
All of the terms have the same form: \(b_i (10^i - 2^i) = b_i 2^i (5^i - 1)\). When \(i \geq 3\) the term clearly has \(2^3 = 8\) as a factor. But what about the smaller terms, when \(i < 3\)? Well, we're in luck:
\begin{array}{l}
b_2(10^2 - 2^2) = b_2(96)\\
b_1(10^1 - 2^1) = b_1(8)\\
b_0(10^0 - 2^0) = b_0(0) \end{array}
Since each of the terms in the sum is a multiple of 8, the sum as a whole is a multiple of 8, which is what we wanted to show.
I think this is a great example of what makes teaching so challenging and exciting for me. I love being surprised by students and by the way they approach mathematics, and I love thinking deeply about so-called "simple" concepts.
I hope to hear from folks in the comments, either here or over at Math Mistakes!
RSS Feed
