Putnam Question (Pigeonhole Principle on divisibility of sequences)

Question

Problem (from page 338 of Putnam and Beyond): Let $x_1 = x_2 = x_3= 1$ and $x_{n+3} = x_n + x_{n+1} x_{n+2}$ for all positive integers $n.$ Prove that for any positive integer $m$ there is an index $k$ such that $m$ divides $x_k$.

Solution: We are allowed by the recurrence relation to set $x_0 = 0.$ We will prove that there is an index $k \leq{m^3}$ such that $x_k$ divided $m.$ Let $r_{t}$ be the remainder obtained by dividing $x_t$ by m for $t = 0,1,\ldots,m^3 + 2.$ Consider the triples ($r_0,r_1,r_2), (r_1,r_2,r_3),\ldots,(r_{m^3},r_{m^3 + 1},r_{m^3 + 2}).$ Since $r_t$ can take m values, the pigeonhole principle implies that at least two triples are equal...

Note: I don't quite understand the last part of the last line of the above paragraph. How does the fact that $r_t$ can have $m$ values, imply that at least two triples are equal. Any help is appreciated.

Answer 1

There are $m^3 + 1$ triples (these are your pigeons) and there exists $m^3$ different configurations for a given triple (these are your holes). By the pigeonhole principle, two triples must be equal.

Answer 2

The pigeonhole principle states that given $p$ pigeons in $h$ holes, if $p>h$, then at least one hole must have two pigeons in it, no matter how you go about your pigeon-stuffing.

The possible remainder-triples$\mod m$ are your holes. There are $m$ congruence classes $\mod m$. So a triple of remainders could take $m^3$ values.

The actual remainder-triples are your pigeons. Note that you can count them by counting the first index (from $0$ to $m^3$) = $m^3 + 1$.

$m^3 + 1 > m^3 \implies p > h \implies \exists h_i,p_a,p_b$ s.t. $p_a\to h_i\land p_b\to h_i$