Pigeonhole Principle to solve problem

RolandIRL

A question posed to us by my lecturer that has me tearing my hair out :mad:

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

i've tried a few examples, like you need to multiply 3 by 37 to produce 111, but i'm not sure how to do it for n.
The first digit has to be 1, and all other digits can be either 1 or 0.

can someone give me a nudge in the right direction or start me off cos i know there's probably some simple way but i'm over complicating it.

thanks

Michael Collins

Nice question. A bit hard maybe if you don't know how to start it. I remember seeing a similar problem that should work here too - it might not be the most clever solution though.

Think of a list of numbers of the form: 1, 11, 111, ..., "k ones", "k+1 ones".

Now divide k into each of these numbers, and note the remainder.

Now think of how many remainders you have...

There's a small jump to make at the end, which I'll leave up to you!

RolandIRL

Michael Collins wrote: »

Nice question. A bit hard maybe if you don't know how to start it. I remember seeing a similar problem that should work here too - it might not be the most clever solution though.

Think of a list of numbers of the form: 1, 11, 111, ..., "k ones", "k+1 ones".

Now divide k into each of these numbers, and note the remainder.

Now think of how many remainders you have...

There's a small jump to make at the end, which I'll leave up to you!

but what about even numbers? they'll never divide into anything ending in 1, or could i have the first digit as one, then the rest as zeroes, then keeping adding zeroes like 1,10,100,1000 etc...never mind. just tried that with six, doesn't work

just had an "aaah" moment there. the n (the multiple of k) will divide into "j ones" where j is less than/equal to n, but this only works if n is odd, right?

need a bit more of a nudge, i think

Michael Collins

OK, let's try it for the number k = 4:

The list we need is then: 1, 11, 111, 1111, 11111.

The remainders when we divide 4 into these are, in order: 1, 3, 3, 3, 3.

Now we can see that we have some remainders that are the same (four remainders equal to 3 in this case), and in general from the Pigeonhole Principle we can see that, since we'll have k+1 remainders of a number k, that can obviously only have k unique nonzero remainders, we necessarily have at least two remainders which are the same.

Now, how do we use this fact to make a number divisible by k?

What can you do to two numbers with the same remainder when divided by x, to make them divisible by x?

Relating to the above example, what can you do to 111 and 11 say (both with remainder = 3), so you have a number divisible by 4?

RolandIRL

ah now i get where you're going. subtract them and the difference is equal to a number divisible by 4.

and now as soon as we get two remainders that are the same for k, since the numbers all end in ........1111111, the difference will mean that there will be no other digits than 0 or 1.

so for any number k, if we take write a sequence as 1, 11, 111,....all the way up to "k+1 ones", and divide each number by k, there will be at least two numbers with the same remainder, and on subtraction, they will only be composed of 1's and 0's. if the remainder is 0, then that number is composed of only 1's.
but how would this relate to the Pigeonhole Principle? it seems to be a different way and i need to use the Principle to get my proof

Michael Collins

The fact that when you have k+1 remainders with each one having k possible values implies two of them must be the same, is a direct use of the Pigeonhole Principle is it not?

k+1 items, k pigeonholes => at least two in the same pigeonhole!

RolandIRL

now i get ya. for k+1 numbers, at least two must have the same remainder when divided by k.

it's just been a long day, trying to figure this and other stuff out Head = wrecked

thanks for all your help

Michael Collins

No bother, glad to be of help.

RolandIRL

just looking back at your first reply, it seems so obvious now

thanks again

ray giraffe

Very tricky question if you hadn't seen something similar before. It is closely related to the fact that every fraction has either a terminating or repeating decimal expansion.

Note also that the OP's result holds not only in base 10, but in base 2 :pac: and indeed any other base.

Michael Collins

ray giraffe wrote: »

Very tricky question if you hadn't seen something similar before. It is closely related to the fact that every fraction has either a terminating or repeating decimal expansion.

Note also that the OP's result holds not only in base 10, but in base 2 :pac: and indeed any other base.

Yeh, not a chance I'd have got that had I not seen a very similar example before. Hmm, do you care to expand on the link to every fraction having a terminating or repeating decimal expansion Ray? I can't see any direct link at the moment, this may have something to do with the fact that it's 1.40am...

whiteman19 wrote: »

just looking back at your first reply, it seems so obvious now

thanks again

That's always the way with maths, stuff you know is eeeeaasy!

ray giraffe

Michael Collins wrote: »

Hmm, do you care to expand on the link to every fraction having a terminating or repeating decimal expansion Ray? I can't see any direct link at the moment, this may have something to do with the fact that it's 1.40am...

I will assume that every fraction has a terminating or repeating decimal expansion and prove the OP's statement.

Suppose we have a fraction c/k in its lowest terms.

If it has a terminating n-digit decimal expansion (n digits after decimal point) then k divides into 10^n, an integer containing only the digits 0 and 1.

Otherwise it has a repeating decimal expansion. It starts to repeat n digits after the decimal point and repeats with period m. Then x:=(10^n)*(c/k) starts to repeat immediately after the decimal point with period m.

Therefore (10^m)*x-x = ((10^m)-1)*x = (99...99)*x =(9...90...0)*(c/k) is an integer, and so k divides z=9...90...0=(10^n)*((10^m)-1). Suppose k does not divide (z/9)=1...10...0=(10^n)*((10^m)-1)/9. We need an extra 9=3^2 in the prime factorization.

Note that 9 divides into
(((10^9m)-1)/9)/(((10^m)-1)/9)=((10^9m)-1)/((10^m)-1), therefore k divides into (10^n)*((10^9m)-1)/9= 1...10...0 as required.

Q.E.D. :cool:

The OP's statement can be generalised nicely to the following.

Let S be any fixed subset of {1,2,3,4,5,6,7,8,9}. Let k be any positive integer. There exists a positive integer multiple n of k such that the set of digits in n is equal to S union {0}.