Prove that the sequence 1967, 19671967, 196719671967,... contains an element that is divisible by 1969.
thanx
let $\displaystyle x_n$ be the n-th term of this sequence, i.e. $\displaystyle x_1=1967, \ x_2=19671967, \ x_3=196719671967, \ \cdots .$ see that if $\displaystyle n > m,$ then: $\displaystyle 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 $\displaystyle n > m$ such that $\displaystyle x_n \equiv x_m \mod 1969.$
hence by (1): $\displaystyle 10^{4m}x_{n-m}=x_n - x_m \equiv 0 \mod 1969,$ which gives us: $\displaystyle x_{n-m} \equiv 0 \mod 1969,$ because obviously: $\displaystyle \gcd(10^k, 1969)=1, \ \forall k \in \mathbb{N} \ \ \ \Box$
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