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!

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.

## Comments

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.

## Trackbacks

One Trackback