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!

2 thoughts on “A challenging arithmetic / number theory problem

  1. 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 )

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