1.3 The Pigeonhole Principle 1340.A chess player trains by playing at least one game per day, but, to avoid exhaustion,
no more than 12 games a week. Prove that there is a group of consecutive days in
which he plays exactly 20 games.
41.Letmbe a positive integer. Prove that among any 2m+1 distinct integers of
absolute value less than or equal to 2m−1 there exist three whose sum is equal
to zero.
42.There arenpeople at a party. Prove that there are two of them such that of the
remainingn−2 people, there are at leastn 2 −1 of them each of whom knows
both or else knows neither of the two.
43.Letx 1 ,x 2 ,...,xkbe real numbers such that the setA={cos(nπ x 1 )+cos(nπ x 2 )+
···+cos(nπ xk)|n≥ 1 }is finite. Prove that all thexiare rational numbers.Particularly attractive are the problems in which the pigeons and holes are geometric
objects. Here is a problem from a Chinese mathematical competition.
Example.Given nine points inside the unit square, prove that some three of them form
a triangle whose area does not exceed^18.
Solution.Divide the square into four equal squares, which are the “boxes.’’ From the
9 = 2 × 4 +1 points, at least 3= 2 +1 will lie in the same box. We are left to show that
the area of a triangle placed inside a square does not exceed half the area of the square.
Cut the square by the line passing through a vertex of the triangle, as in Figure 3.
Since the area of a triangle isbase× 2 heightand the area of a rectangle is base×height, the
inequality holds for the two smaller triangles and their corresponding rectangles. Adding
up the two inequalities, we obtain the inequality for the square. This completes the
solution.
Figure 344.Inside a circle of radius 4 are chosen 61 points. Show that among them there are
two at distance at most√
2 from each other.