Advanced book on Mathematics Olympiad

Methods of Proof 329 17.We prove both parts by induction onn. For (a), the casen=1 is straightforward. Assume now that we have f ...

330 Methods of Proof With indices taken modulok+1, there exist two termsxjandxj+ 1 such thatxj>0, xj+ 1 <0, andxj+xj+ 1 &g ...

Methods of Proof 331 It is straightforward to check that thegandhconstructed this way satisfy the required condition. (Kvant(Qua ...

332 Methods of Proof We do so by induction onn. The inductive argument will assume the property to be true forn=k−1 andn=k, and ...

Methods of Proof 333 Figure 44 This proves the identity. Settingm=n=p, we obtain the identity in the statement. 26.The base case ...

334 Methods of Proof colored by a third color (Figure 46). The new diagonal dissects the polygon into two poly- gons satisfying ...

Methods of Proof 335 1 = 12 , 2 =− 12 − 22 − 32 + 42 , 3 =− 12 + 22 , 4 =− 12 − 22 + 32. The inductive step is “P (n)impliesP(n+ ...

336 Methods of Proof This is clearly the same as f ( x 1 +x 2 +···+xn− 1 n− 1 ) = f(x 1 )+x 2 +···+f(xn− 1 ) n− 1 , and the argu ...

Methods of Proof 337 Two of the numbers fall in the same set; their sum is equal to 99. We are done. 34.As G. Pólya said, “a tri ...

338 Methods of Proof We apply now the pigeonhole principle, letting the “objects’’ be all pairs of consec- utive Fibonacci numbe ...

Methods of Proof 339 Remark.In general, if a chess player decides to playdconsecutive days, playing at least one game a day and ...

340 Methods of Proof | |≥ n(n− 1 )(n− 3 ) 2 . To apply the pigeonhole principle, we let the “holes’’ be the ordered pairs of peo ...

Methods of Proof 341 inscribed in an 8×8 square decomposed into 64 unit squares. Because 3^2 + 32 > 42 , the four unit square ...

342 Methods of Proof 47.Ann-gon has (n 2 ) −n=^12 n(n− 3 )diagonals. Forn=21 this number is equal to If through a point in the ...

Methods of Proof 343 Next, look at the lineA 2. Either there is a rectangle of colorc 1 , or at most one point M 2 jis colored b ...

344 Methods of Proof D(O 1 ,r 1 ), D(O 2 ,r 2 ),...,D(On,rn), in decreasing order of their radii. Choose the diskD(O 1 ,r 1 ), a ...

Methods of Proof 345 a+b+c> 4 d. Let us look at the situation in whichdisa 3 anda, b, andcarea 1 ,a 2 , anda 4. The inequalit ...

346 Methods of Proof 57.Again, there will be an interplay between the indices and the values of the terms. We start by ordering ...

Methods of Proof 347 ...... P P P i Pj M j+ (^1) i+ 1 Figure 52 60.LetAiAi+ 1 be the longest side of the polygon (or one of them ...

348 Methods of Proof 62.Letbbe a boy dancing with the maximal number of girls. There is a girlg′he does not dance with. Choose a ...