Advanced book on Mathematics Olympiad

Methods of Proof 339

Remark.In general, if a chess player decides to playdconsecutive days, playing at
least one game a day and a total of no more thanmwithd<m< 2 d, then for each
i≤ 2 d−n−1 there is a succession of days on which, in total, the chess player played
exactlyigames.
(D.O. Shklyarskyi, N.N. Chentsov, I.M. Yaglom,Izbrannye Zadachi i Theoremy El-
ementarnoy Matematiki(Selected Problems and Theorems in Elementary Mathematics),
Nauka, Moscow, 1976)

41.The solution combines the induction and pigeonhole principles. We commence with
induction. The base casem=1 is an easy check, the numbers can be only− 1 , 0 ,1.
Assume now that the property is true for any 2m−1 numbers of absolute value
not exceeding 2m−3. LetAbe a set of 2m+1 numbers of absolute value at most
2 m−1. IfAcontains 2m−1 numbers of absolute value at most 2m−3, then we
are done by the induction hypothesis. Otherwise,Amust contain three of the numbers
±( 2 m− 1 ),±( 2 m− 2 ). By eventually changing signs we distinguish two cases.

CaseI. 2m− 1 ,− 2 m+ 1 ∈A. Pair the numbers from 1 through 2m−2as( 1 , 2 m−

2 ),( 2 , 2 m− 3 ),...,(m− 1 ,m), so that the sum of each pair is equal to 2m−

1, and the numbers from 0 through− 2 m+1as( 0 ,− 2 m+ 1 ), (− 1 ,− 2 m+

2 ),...,(−m+ 1 ,−m), so that the sum of each pair is− 2 m+1. There are

2 m−1 pairs, and 2melements ofAlie in them, so by the pigeonhole principle

there exists a pair with both elements inA. Those elements combined with

either 2m−1or− 2 m+1 give a triple whose sum is equal to zero.

CaseII. 2m− 1 , 2 m− 2 ,− 2 m+ 2 ∈Aand− 2 m+ 1 ∈/A.If0∈A, then 0− 2 m+
2 + 2 m− 2 =0 and we are done. Otherwise, consider the pairs( 1 , 2 m−
3 ), ( 2 , 2 m− 4 ),...,(m− 2 ,m), each summing up to 2m−2, and the pairs
( 1 ,− 2 m),...,(−m+ 1 ,−m), each summing up to− 2 m+1. Altogether there
are 2m−2 pairs containing 2m−1 elements fromA, so both elements of some
pair must be inA. Those two elements combined with either− 2 m+2or2m− 1
give a triple with the sum equal to zero. This concludes the solution.
(Kvant(Quantum))

42.Denote by the set of ordered triples of people(a,b,c)such thatcis either a
common acquaintance of bothaandbor unknown to bothaandb.Ifcknows exactly
kparticipants, then there exist exactly 2k(n− 1 −k)ordered pairs in whichcknows
exactly one ofaandb(the factor 2 shows up because we work withorderedpairs). There
will be

(n− 1 )(n− 2 )− 2 k(n− 1 −k)≥(n− 1 )(n− 2 )− 2

(

n− 1

2

) 2

=

(n− 1 )(n− 3 )

2

ordered pairs(a, b)such thatcknows either both or neither ofaandb. Counting by the
c’s, we find that the number of elements of satisfies