324 Methods of Proof
3.The example 2^2 , 32 , 52 ,..., 432 , where we considered the squares of the first 14 prime
numbers, shows thatn≥15.
Assume that there exista 1 ,a 2 ,...,a 16 , pairwise relatively prime integers greater than
1 and less than 2005, none of which is a prime. Letqkbe the least prime number in the
factorization ofak,k= 1 , 2 ,...,16. Letqibe the maximum ofq 1 ,q 2 ,...,q 15. Then
qi≥p 16 =47. Becauseaiis not a prime,aqiiis divisible by a prime number greater than
or equal toqi. Henceai≥qi^2 = 472 >2005, a contradiction. We conclude thatn=15.
4.Arguing by contradiction, we assume that none of the colors has the desired property.
Then there exist distancesr≥g≥bsuch thatris not attained by red points,gby green
points, andbby blue points (for these inequalities to hold we might have to permute the
colors).
Consider a sphere of radiusrcentered at a red point. Its surface has green and blue
points only. Sinceg, b≤r, the surface of the sphere must contain both green and blue
points. ChooseMa green point on the sphere. There exist two pointsPandQon the
sphere such thatMP=MQ=gandPQ=b. So on the one hand, eitherPorQis
green, or elsePandQare both blue. Then either there exist two green points at distance
g, namelyMandP,orQ, or there exist two blue points at distanceb. This contradicts
the initial assumption. The conclusion follows.
(German Mathematical Olympiad, 1985)
5.Arguing by contradiction, let us assume that the area of the overlap of any two sur-
faces is less than^19. In this case, ifS 1 ,S 2 ,...,Sndenote the nine surfaces, then the area
ofS 1 ∪S 2 is greater than 1+^89 , the area ofS 1 ∪S 2 ∪S 3 is greater than 1+^89 +^79 ,...,
and the area ofS 1 ∪S 2 ∪···∪S 9 is greater than
1 +
8
9
+
7
9
+···+
1
9
=
45
9
= 5 ,
a contradiction. Hence the conclusion.
(L. Panaitopol, D. ̧Serbanescu, ̆ Probleme de Teoria Numerelor ̧si Combinatorica
pentru Juniori(Problems in Number Theory and Combinatorics for Juniors), GIL, 2003)
6.Assume that such anfexists. We focus on some particular values of the variable. Let
f( 0 )=aandf( 5 )=b,a, b∈{ 1 , 2 , 3 },a =b. Because| 5 − 2 |=3,| 2 − 0 |=2, we
havef( 2 ) =a, b,sof( 2 )is the remaining number, sayc. Finally, because| 3 − 0 |=3,
| 3 − 5 |=2, we must havef( 3 )=c. Therefore,f( 2 )=f( 3 ). Translating the argument
to an arbitrary numberxinstead of 0, we obtainf(x+ 2 )=f(x+ 3 ), and sofis constant.
But this violates the condition from the definition. It follows that such a function does
not exist.
7.Arguing by contradiction, let us assume that such a function exists. Setf( 3 )=k.
Using the inequality 2^3 < 32 , we obtain