Advanced book on Mathematics Olympiad

346 Methods of Proof

57.Again, there will be an interplay between the indices and the values of the terms.
We start by ordering theai’s increasinglya 1 <a 2 <···<an. Because the sum of
two elements ofXis inX, givenaiin the complement ofX, for each 1≤m≤a 2 i, either
morai−mis not inX. There area 2 isuch pairs and onlyi−1 integers less thanaiand
not inX; henceai≤ 2 i−1. Summing overigivesa 1 +a 2 +···+an≤n^2 as desired.
(In the solution we denoted byxthe least integer greater than or equal tox.)
(proposed by R. Stong for the USAMO, 2000)
58.Call the elements of the 4×4 tableauaij,i, j= 1 , 2 , 3 ,4, according to their location.
As such,a 13 =2,a 22 =5,a 34 =8 anda 41 =3. Look first at the row with thelargest
sum, namely, the fourth. The unknown entries sum up to 27; hence all three of them,
a 42 ,a 43 , anda 44 , must equal 9. Now we consider the column withsmallestsum. It is the
third, with

a 13 +a 23 +a 33 +a 43 = 2 +a 23 +a 33 + 9 = 13.

We see thata 23 +a 33 =2; therefore,a 23 =a 33 =1. We than have

a 31 +a 32 +a 33 +a 34 =a 31 +a 32 + 1 + 8 = 26.

Therefore,a 31 +a 32 =17, which can happen only if one of them is 8 and the other is 9.

Checking the two cases separately, we see that onlya 31 =8,a 32 =9 yields a solution,

which is described in Figure 51.

Figure 51

(such puzzles appear in the Sunday edition of theSan Francisco Chronicle)

59.There are only finitely many polygonal lines with these points as vertices. Choose

the one of minimal lengthP 1 P 2 ...Pn. If two sides, sayPiPi+ 1 andPjPj+ 1 , intersect

at some pointM, replace them byPiPj andPi+ 1 Pj+ 1 to obtain the closed polygonal

lineP 1 ...PiPjPj− 1 ...Pi+ 1 Pj+ 1 ...Pn(Figure 52). The triangle inequality in triangles

MPiPjandMPi+ 1 Pj+ 1 shows that this polygonal line has shorter length, a contradiction.

It follows thatP 1 P 2 ...Pnhas no self-intersections, as desired.