# Does the Pigeonhole principle apply in this problem?

I came accross this problem a while ago at school during a math contest. I dont remember the exact instruction (word for word) but it went something like :

Randomed A and B, 2 natural integer $\in [0,100]$ , Start a Fibonacci-like sequence.

A + B => C
B + C => D
etc.


If the sum goes stricly above 100, trim the first digit(leaving only the tens and units) and go on. Proove that no matter what are the two random numbers at start, the sequence will repeat itself at some point.

I thought at the time that the Pigeonhole principle could help me proove this easily but I never achieved it. Any help on this problem would be great. Sorry for the lack of mathematical vocabulary, english isn't my native langage and technical vocabulary is hard to use correctly.

• Whenever you have a pair $(a_n,\, a_{n-1})$ that you've seen before, you found a loop. How many possible pairs are there? Commented Jul 31, 2013 at 14:15
• i Count 101² of them Commented Jul 31, 2013 at 14:26

Look at the sequence of couples of consecutive terms. Observe that given two numbers $(a,b)$, the rest of the sequence is fully determined; therefore, it is sufficient to prove that no matter what are the initial two numbers, as some point you will fall back to two successive terms of the sequence $(a^\prime,b^\prime)$ previously encountered. Then the pigeonhole principle applies, since your numbers are always in $\{0,\dots,100\}$ — you have only $101^2$ possible different couples $(a,b)$, but your sequence of couples has infinitely many terms.
• How do you count 101² different couple ? I counted $99!$, what did I do wrong ? Commented Jul 31, 2013 at 14:23
• @WizardLizard, in the couple $(a, b)$, $a$ and $b$ must come from $\{0, \ldots, 100\}$; hence, there are $101$ possibilities for each, and $101^{2}$ possible different couples. However, even if it were $99!$, that's still finite. Commented Jul 31, 2013 at 14:26
The sequence will repeat itself. This is the pisano period of the integer $n=100$ (assuming that you disallow $a,b=100$).