Results 1 to 4 of 4

Math Help - Pigeon Hole Help needed

  1. #1
    Newbie
    Joined
    Oct 2008
    Posts
    7

    Pigeon Hole Help needed

    Prove that the sequence 1967, 19671967, 196719671967,... contains an element that is divisible by 1969.

    thanx
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by dajaka View Post
    Prove that the sequence 1967, 19671967, 196719671967,... contains an element that is divisible by 1969.
    thanx
    let x_n be the n-th term of this sequence, i.e. x_1=1967, \ x_2=19671967, \ x_3=196719671967, \ \cdots . see that if n > m, then: x_n - x_m =10^{4m}x_{n-m}. \ \ \ \ \ \ (1)

    now the sequence is infinite and we know that modulo 1969 there are only 1969 distinct integers. therefore there exist n > m such that x_n \equiv x_m \mod 1969.

    hence by (1): 10^{4m}x_{n-m}=x_n - x_m \equiv 0 \mod 1969, which gives us: x_{n-m} \equiv 0 \mod 1969, because obviously: \gcd(10^k, 1969)=1, \ \forall k \in \mathbb{N} \ \ \ \Box
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2008
    Posts
    7
    thanx
    i think pigeonhole is used, right?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Oct 2008
    Posts
    8
    Quote Originally Posted by dajaka View Post
    thanx
    i think pigeonhole is used, right?
    Yes man the pigeonhole is used! in term of remainders,

    Try to look at this link A Walk Through Combinatorics: An ... - Google Ricerca Libri

    The first chapter is about this principle and you can find a more detailed proof reletaed to this problem. It is the first of them. page 2.

    Bye
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 2nd 2011, 02:44 PM
  2. pigeon-hole
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: December 11th 2008, 01:41 PM
  3. Pigeon hole-proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 11th 2008, 01:02 AM
  4. big pigeon hole question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 11th 2007, 11:19 AM
  5. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 30th 2007, 08:37 AM

Search Tags


/mathhelpforum @mathhelpforum