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

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
6 replies · 6K views
whiteman
Messages
8
Reaction score
0

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 :)
 
Physics news on Phys.org
Dick said:
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.
 
jbunniii said:
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.
 
Last edited:
Dick said:
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,...}?
 
aldebaran19 said:
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'.
 
thanks for all the help, guys, especially Dick. i was able to get it from the first post you gave :)