Collaborative Mathematics

Learning from student "mistakes", part 2

4/11/2013

1 Comment

 
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:
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!
1 Comment
Hao Ye
22/11/2013 03:55:19 pm

Some neat things to note:
(1) (x^n - y^n) = (x - y) * (x^(n-1) + x^(n-2)*y + x^(n-3)*y^2 + ... + y^(n-1))
[This is one quick way to note that 10^n - 2^n is a multiple of 8.]
(2) If we want to know whether b_{n}*10^n + b_{n-1}*10^{n-1} + ... + b_{0}*10^{0} is the same as b_{n}*2^n + b_{n-1}*2^{n-1} + ... + b_{0}*2^{0} modulo 8, we can replace 10 in the first equation with 2, because 10 and 2 are the same modulo 8, and it's pretty obvious from there. (A basic property of modular arithmetic is that we can simplify addends, multiplicands, and bases of exponentiation [because they're the same as multiplicands].)

Reply



Leave a Reply.

    CollaboMath:
    The Blog

    Jason Ermer is a mathematics and computer science teacher living in Oslo, Norway.

    Archives

    February 2015
    January 2015
    December 2014
    November 2014
    October 2014
    September 2014
    May 2014
    April 2014
    March 2014
    February 2014
    January 2014
    December 2013
    November 2013
    October 2013
    September 2013

    Categories

    All
    Challenge01
    Challenge03
    Challenge04
    Challenge05
    Challenge06
    Challenge07
    Challenge08
    Challenge09
    Challenge10
    Challenge11
    Challenge12
    Challenge13
    Challenge14
    Mtbos
    Problems
    Videochallenges
    Videoresponses

    RSS Feed

Challenge Archive
About the Project
Contact Us
Credits
Creative Commons License
Except where otherwise noted, this work by Jason Ermer is licensed
under a Creative Commons Attribution-ShareAlike 3.0 Unported License.
Proudly powered by Weebly