Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

Pigeonhole Principle to solve problem

  • 25-10-2010 12:45pm
    #1
    Closed Accounts Posts: 11,924 ✭✭✭✭


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


Comments

  • Moderators, Science, Health & Environment Moderators Posts: 1,852 Mod ✭✭✭✭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!


  • Closed Accounts Posts: 11,924 ✭✭✭✭RolandIRL


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


  • Moderators, Science, Health & Environment Moderators Posts: 1,852 Mod ✭✭✭✭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?


  • Closed Accounts Posts: 11,924 ✭✭✭✭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 :/


  • Moderators, Science, Health & Environment Moderators Posts: 1,852 Mod ✭✭✭✭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!


  • Advertisement
  • Closed Accounts Posts: 11,924 ✭✭✭✭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 :o Head = wrecked

    thanks for all your help :)


  • Moderators, Science, Health & Environment Moderators Posts: 1,852 Mod ✭✭✭✭Michael Collins


    No bother, glad to be of help.


  • Closed Accounts Posts: 11,924 ✭✭✭✭RolandIRL


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

    thanks again :)


  • Registered Users, Registered Users 2 Posts: 338 ✭✭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.


  • Moderators, Science, Health & Environment Moderators Posts: 1,852 Mod ✭✭✭✭Michael Collins


    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 :o

    thanks again :)

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


  • Advertisement
  • Registered Users, Registered Users 2 Posts: 338 ✭✭ray giraffe


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


Advertisement