Results 1 to 8 of 8

Math Help - More pigeons?

  1. #1
    Member billym's Avatar
    Joined
    Feb 2008
    Posts
    183

    More pigeons?

    Surely this is a basic problem. I have no idea how to start.

    "n is any positive integer. Show that there is a positive integer k which is a multiple of n which consists entirely of 1's and 0's."

    I have no idea how to start. Can somebody kick me?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Reply

    Theorem 1 : A non-zero number has infinitely many multiples.
    Theorem 2 : A non-zero number has at least one divisor.
    Theorem 3 : There are infinitely many numbers.

    Therefore, according to Theorems 1 & 3, the set of all multiples of n (an infinity) must contain infinitely many numbers composed of 0's and 1's. Because of Theorem 2, these numbers have at least one divisor, and since they are infinitely many, there is a probability of 1 that n is a divisor of one of these numbers.

    I don't know if this is "mathematically" correct, though.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by Bacterius View Post
    Theorem 1 : A non-zero number has infinitely many multiples.
    Theorem 2 : A non-zero number has at least one divisor.
    Theorem 3 : There are infinitely many numbers.

    Therefore, according to Theorems 1 & 3, the set of all multiples of n (an infinity) must contain infinitely many numbers composed of 0's and 1's. Because of Theorem 2, these numbers have at least one divisor, and since they are infinitely many, there is a probability of 1 that n is a divisor of one of these numbers.

    I don't know if this is "mathematically" correct, though.
    Both of these statements are wrong. The fact that a number has infinite integer multiples does not necessarily mean one of those integers will consist of the digits 0,1. Using the same logic we could reach the false conclusion that every positive integer has a multiple which consists solely of the digits 7,1 - which is not true.

    Also, the multiples of n are divided by it because, well, they are multiples of it (this is how you defined them)... However, the fact that they are infinite does not necessarily mean n will divide one of them. Take, for example, the following infinite sequence of multiples:

    \{a_n\}_{n=1}^{\infty} : \  a_i = 7^i \ \forall i \geq 1

    Then this is an infinite sequence of multiples of seven, but none of them are divided by 5!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Oct 2009
    From
    Brisbane
    Posts
    311
    Thanks
    2
    Works in binary
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927

    Reply

    This is why I said I wasn't sure it worked mathematically. It doesn't, yet those type of questions can get hard sometimes, eh ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    An integer consisting in only 0's and 1's is a sum of 10^k, for some k\in\mathbb{N}. Let n be a positive integer,

    we want to prove there are integers k_1,...,k_m such that \sum\limits_{i=1}^m10^{k_i}=0\mod n.

    For all k\in\mathbb{N}, there is an 0\leq i<n such that i\equiv 10^k\mod n. What if we consider these i for 0\leq k\leq n^{n-1} (here come the pigeons)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    I think this may be equivalent to clic-clac's hint (I'm not sure), but here is another approach anyway:

    Consider the n+1 integers 1, 11, 111, ..., on up to n+1 repetitions of 1.
    There are n congruence classes modulo n, so at least two of these integers must be in the same congruence class. Then...
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    I don't think it is equivalent, your way is just far prettier and easier than mine!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum