A positive multiple of any positive integer exists that only has the digits {0,1}

  • Thread starter whiteman
  • Start date
1. The problem statement, all variables and given/known data
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.)


2. Relevant 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.


3. 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

Science Advisor
Homework Helper
26,251
613
Think about the sequence of numbers {1,11,111,1111,11111,...}. How many possible remainders are there when you divide by k?
 

jbunniii

Science Advisor
Homework Helper
Insights Author
Gold Member
3,384
179
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

Science Advisor
Homework Helper
26,251
613
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:
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

Science Advisor
Homework Helper
26,251
613
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 :)
 

Want to reply to this thread?

"A positive multiple of any positive integer exists that only has the digits {0,1}" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Latest threads

Top