A challenging arithmetic / number theory problem

While visiting MIT on Thursday I stumbled on this really interesting problem:

Show that any positive integer n 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 n.

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 n, how do we find a multiple of n with only 1’s and 0’s?

Finally, we wrap up by exploring a few other similar ideas – for example, do all positive integers n 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!



One Comment so far. Leave a comment below.
  1. Andrew Gacek,

    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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: