Advanced book on Mathematics Olympiad

338 Methods of Proof

We apply now the pigeonhole principle, letting the “objects’’ be all pairs of consec-

utive Fibonacci numbers(Fn,Fn+ 1 ),n≥1, and the “boxes’’ the pairs of residue classes

modulon. There are infinitely many objects, and onlyn^2 boxes, and so there exist indices

i>j>1 such thatFi≡Fj(modn)andFi+i≡Fj+ 1 (modn).

In this case

Fi− 1 =Fi+ 1 −Fi≡Fj+ 1 −Fj=Fj− 1 (modn),

and henceFi− 1 ≡Fj− 1 (modn)as well. An inductive argument proves thatFi−k≡

Fj−k(modn),k= 1 , 2 ,...,j. In particular,Fi−j ≡F 0 = 0 (modn). This means

thatFi−jis divisible byn. Moreover, the indicesiandjrange in an infinite family, so

the differencei−jcan assume infinitely many values. This proves our claim, and as a

particular case, we obtain the conclusion of the problem.

(Irish Mathematical Olympiad, 1999)

39.We are allowed by the recurrence relation to setx 0 =0. We will prove that there is

an indexk≤m^3 such thatxkdividesm. Letrtbe the remainder obtained by dividing

xt bymfort = 0 , 1 ,...,m^3 +2. Consider the triples(r 0 ,r 1 ,r 2 ),(r 1 ,r 2 ,r 3 ),...,

(rm 3 ,rm (^3) + 1 ,rm (^3) + 2 ). Sincertcan takemvalues, the pigeonhole principle implies that at
least two triples are equal. Letpbe the smallest number such that the triple(rp,rp+ 1 ,rp+ 2 )
is equal to another triple(rq,rq+ 1 ,rq+ 2 ),p<q≤m^3. We claim thatp=0.
Assume by way of contradiction thatp≥1. Using the hypothesis, we have
rp+ 2 ≡rp− 1 +rprp+ 1 (modm) and rq+ 2 ≡rq− 1 +rqrq+ 1 (modm).
Becauserp =rq,rp+ 1 = rq+ 1 , andrp+ 2 =rq+ 2 , it follows thatrp− 1 =rq− 1 ,so
(rp− 1 ,rp,rp+ 1 )=(rq− 1 ,rq,rq+ 1 ), contradicting the minimality ofp. Hencep=0, so
rq=r 0 =0, and thereforexqis divisible bym.
(T. Andreescu, D. Mihe ̧t)
40.We focus on 77 consecutive days, starting on a Monday. Denote byanthe number
of games played during the firstndays,n≥1. We consider the sequence of positive
integers
a 1 ,a 2 ,...,a 77 ,a 1 + 20 ,a 2 + 20 ,...,a 77 + 20.
Altogether there are 2× 77 =154 terms not exceeding 11× 12 + 20 =152 (here we took
into account the fact that during each of the 11 weeks there were at most 12 games). The
pigeonhole principle implies right away that two of the above numbers are equal. They
cannot both be among the first 77, because by hypothesis, the number of games increases
by at least 1 each day. For the same reason the numbers cannot both be among the last

77. Hence there are two indiceskandmsuch thatam=ak+20. This implies that in
    the time interval starting with the(k+ 1 )st day and ending with thenth day, exactly 20
    games were played, proving the conclusion.