While visiting MIT on Thursday I stumbled on this really interesting problem:
Show that any positive integer has a (positive) multiple which has only the digits 1 and 0 when represented in base 10.
This is – obviously – not a problem intended for kids, but I thought that it would be fun to talk through it with them since the ideas in the solution are actually accessible to kids.
Here’s the introduction to the problem and a few initial thoughts from my kids:
After their initial thoughts we moved on to talking about the solution. The first step involves looking at numbers that only have 1’s. This step gives us a nice opportunity to talk about remainders.
Also, finding a way to describe the patter in the remainders is a nice challenge for the kids.
Now that we’ve understood a little bit about the remainders, we move to the key idea in the solution – as we look through the numbers 1, 11, 111, and etc, we’ll eventually find two numbers that have the same remainder when we divide by .
This is a challenging idea for kids to understand, but we make some nice progress towards understanding that idea. It is a surprise application of the Pigeonhole Principle.
Now for the last step in the solution – once we find a two numbers in the list 1, 11, 111, 1111, and etc with the same remainder when we divide by , how do we find a multiple of with only 1’s and 0’s?
Finally, we wrap up by exploring a few other similar ideas – for example, do all positive integers have a multiple consisting of only 3’s and 0’s? How about one consisting of only 2’s and 3’s?
So, a really neat (though advanced) math idea that kids can understand. Working through this problem is a nice way to talk about remainders and also about place value. I don’t go through problems like this one very often, but with the right problem it is neat to be able to talk about some advanced ideas with kids!
2 thoughts on “A challenging arithmetic / number theory problem”
That’s better than my solution. I took the numbers 1, 10, 100, 1000, etc. I used the pigeonhole principle to say eventually n of them have the same remainder mod n. Then add those up to get your number.