Methods of Proof 337Two of the numbers fall in the same set; their sum is equal to 99. We are done.
34.As G. Pólya said, “a trick applied twice becomes a technique.’’ Here we repeat the
idea of the Mongolian problem from the 26th International Mathematical Olympiad.
Letb 1 ,b 2 ,...,bmbe the sequence, wherebi ∈{a 1 ,a 2 ,...,an},1≤i≤m. For
eachj≤mdefine then-tupleKj=(k 1 ,k 2 ,...,kn), whereki=0ifaiappears an even
number of times inb 1 ,b 2 ,...,bjandki=1 otherwise.
If there existsj≤msuch thatKj=( 0 , 0 ,..., 0 )thenb 1 b 2 ···bjis a perfect square
and we are done. Otherwise, there existj<lsuch thatKj=Kl. Then in the sequence
bj+ 1 ,bj+ 2 ,...,bleachaiappears an even number of times. The productbj+ 1 bj+ 2 ···bl
is a perfect square.
35.The sequence has the property that for anynthe firstn+1 terms are less than or
equal to 2n. The problem would be solved if we showed that given a positive integern,
from anyn+1 distinct integer numbers between 1 and 2nwe can choose two whose
difference isn. This is true, indeed, since the pigeonhole principle implies that one of
thenpairs( 1 ,n+ 1 ), ( 2 ,n+ 2 ),...,(n, 2 n)contains two terms of the sequence.
(Austrian–Polish Mathematics Competition, 1980)
36.The “holes’’ will be the residue classes, and the pigeons, the numbersax^2 ,c−by^2 ,
x, y= 0 , 1 ,...,p−1. There are 2psuch numbers. Any residue class, except for 0, can
have at most two elements of the formax^2 and at most two elements of the formc−by^2
from the ones listed above. Indeed,ax 12 ≡ax^22 impliesx^21 ≡x^22 ,so(x 1 −x 2 )(x 1 +x 2 )≡0.
This can happen only ifx 1 =±x 2. Also,ax^2 ≡0 only whenx=0.
We distinguish two cases. Ifc−by 02 ≡0 for somey 0 , then( 0 ,y 0 )is a solution.
Otherwise, the 2p−1 numbersax^2 ,c−by^2 ,x= 1 , 2 ,...,p− 1 ,y= 0 , 1 ,...,p−1 are
distributed intop−1 “holes,’’ namely the residue classes 1, 2 ,...,p−1. Three of them
must lie in the same residue class, so there existx 0 andy 0 withax^20 ≡c−by^20 (modp).
The pair(x 0 ,y 0 )is a solution to the equation from the statement.
Remark.A more advanced solution can be produced based on the theory of quadratic
residues.
37.In any 2×2 square, only one of the four numbers can be divisible by 2, and only
one can be divisible by 3. Tiling the board by 2×2 squares, we deduce that at most 25
numbers are divisible by 2 and at most 25 numbers are divisible by 3. There are at least
50 remaining numbers that are not divisible by 2 or 3, and thus must equal one of the
numbers 1, 5, or 7. By the pigeonhole principle, one of these numbers appears at least
17 times.
(St. Petersburg City Mathematical Olympiad, 2001)
38.A more general property is true, namely that for any positive integernthere exist
infinitely many terms of the Fibonacci sequence divisible byn.