Pigeon Hole Help needed

**dajaka** · October 24th 2008, 12:39 PM

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

thanx

**NonCommAlg** · October 24th 2008, 07:20 PM

Originally Posted by dajaka

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$

**dajaka** · October 25th 2008, 12:35 AM

thanx
i think pigeonhole is used, right?

**joksy** · November 4th 2008, 11:12 AM

Originally Posted by dajaka

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

Thread: Pigeon Hole Help needed

LinkBack

Thread Tools

Display

Pigeon Hole Help needed

Similar Math Help Forum Discussions

Pigeon Hole Principle

pigeon-hole

Pigeon hole-proof

big pigeon hole question

Pigeon hole principle

Search Tags