Proving Existence of Positive Integer Multiple with 0s & 1s

[whiteman]

Homework Statement

Let k be any positive integer. Prove that there exists a positive
integer multiple n of k such that the only digits in n are 0s and
1s. (Use the pigeonhole principle.)

Homework Equations

The General Pigeonhole Principle
If more than mk things are distributed into k boxes then
at least one box receives more than m things.

The Attempt at a Solution

Don't know where to start off. I just need a bit of a nudge and hopefully that'll get me started. thanks :)

 

[Dick]

Think about the sequence of numbers {1,11,111,1111,11111,...}. How many possible remainders are there when you divide by k?

 

[jbunniii]

Think about the sequence of numbers {1,11,111,1111,11111,...}. How many possible remainders are there when you divide by k?

Very nice! I thought about this problem on the drive home and came up with a solution, but it's a bit more complicated, entailing two cases depending on whether 10 is a unit or a zero divisor mod k. Your solution is much quicker and more elementary. On the other hand, I think my method might find the smallest possible answer, but I haven't written down the details yet.

 

[Dick]

Very nice! I thought about this problem on the drive home and came up with a solution, but it's a bit more complicated, entailing two cases depending on whether 10 is a unit or a zero divisor mod k. Your solution is much quicker and more elementary. On the other hand, I think my method might find the smallest possible answer, but I haven't written down the details yet.

Yeah, it is nice. This is sort of a classic problem, I've seen it at least once before. It's classic pigeonhole. I didn't make up the solution. I just remembered it. I hadn't even thought about finding the smallest solution. If you can do that it would be interesting.

 

[aldebaran19]

Think about the sequence of numbers {1,11,111,1111,11111,...}. How many possible remainders are there when you divide by k?

This is an interesting question but can't figure out what to do! What do you do with the sequence {1,11,111,...}?

 

[Dick]

This is an interesting question but can't figure out what to do! What do you do with the sequence {1,11,111,...}?

You don't do anything in particular with it as a sequence. You just think about the possible values of the remainders after dividing by k of those values. Then think 'pigeonhole principle'.

 

[whiteman]

thanks for all the help, guys, especially Dick. i was able to get it from the first post you gave :)