Thursday, January 22, 2009

A Presidential Contest Digit Problem: Fours are Wild!

With MathNotation's First Math Contest less than two weeks away (look here for details), I wanted to provide another sample contest question (multi-part). By the way, we now have several middle schools, high schools and even homeschool teams registered from all overv the country! It takes only a few minutes to register and there's still time!
For President Obama, the number four has special significance. The most obvious is that he's the 44th president. You can ask your students to think of several other connections between our new president and the number four. But for now, we will focus on 44...

(a) Since 44 = 2^5 + 2^3 + 2^2, 44 equals 101100 in base 2 (binary representation).
Let S be the set of all base-10 numbers (positive integers) whose binary representation consists of six digits, exactly three of which are 1's. Find the sum of these base-10 numbers to reveal part of the mystery behind the title of this post!
Note that the leftmost binary digit must be "1".

Comment: This is a fairly straightforward 'counting' problem accessible to middle schoolers as well as older students. One could simply make a list of the numbers and add them. However, there's a more systematic way to count the 'combinations' and a "different" way of adding here that may help you solve the next problem. Can you find it?

(b) Consider the set of all base-10 numbers (positive integers) whose binary representation consists of ten digits, exactly three of which are 1's. Show that the sum of these base-10 numbers can be written 44(2^9) - 4 - 4. "Fours are wild!"

Note: This seems like a tedious generalization of Part I, but, again, if you find the right way to count and add it won't take long!

BTW, if you're wondering how I came to find all these 4's, well, it might have been serendipity. After all, serendipity has 11 letters and 11 is a factor of 44 and... (Twilight Zone music playing in the background...). Also, if you're wondering what my outside sources for these kinds of problems are, do you really think there's anyone else out there whose mind could be this warped!


runiteking1 said...

I'm just going to do the second part:
The 10-digit number will be in the form of 1+(nine other digits), thus we will need to distribute only 2 other 1's in there. The crux move to find the sum is to notice that each digit will happen only 8 times when that particular digit is one, once to pair with the other digits. Thus, we can convert the binary to base 10 and multiply each digit by 8:

8(2^8) + 8(2^7) + ... + 8(2^0)

using geometric sum, it becomes 8(2^9 - 1). But we undercounted as we left out the leading one, there a total of 9 nCr 2 numbers, so (9 nCr 2)*2^9 = 36*2^9

summing the two parts up give 44(2^9) - 4 - 4

Dave Marain said...

Nice job, runiteking1!
If you were participating in our contest and submitted this explanation as a solution, you would receive the maximum score for that part of the question. It is difficult to convey the solution here just with words and symbols but you succeeded. Thank you.

Of course my silliness with the 4's is trivial compared to the meaningful mathematics underlying this question:
understanding binary notation (and representations in other bases in general), recognizing that the distribution of the remaining 1's is an nCr problem, recognizing that the remaining 1's would be uniformly distributed in the other "places", summing the numbers 'vertically' by place values rather than 'horizontally', using the geometric sum formula for the powers of 2 etc.

I hope this gave a feel for the kinds of questions I might ask although this specific topic may not be tested this time around.