3.3 THE PIGEONHOLE PRINCIPLE 91- Next, "lift" each region up, with its lattice square. Think of each region as a
picture drawn on a unit square. Stack these squares in a pile, as shown. Now
imagine that we stick a pin through the squares, so that the pin pierces each
square in the same place. Because the area of S is greater than 1, it must be
possible to find a point such that the pin through that point pierces at least
two subregions. In our example, the pin pierces both a and c. point, then thetotal area of S would be less than or equal to the area of a single unit square.
Another way to think of it: imagine cutting out the subregions with a scissor
and trying to stack them all in a unit square, without any overlapping. It would
be impossible, since the total area is greater than 1. (By the same reasoning,
if the total area were greater than the integer n, it would be possible to find a
point where the pin pierces at least n + 1 subregions.)- Finally, we keep track of the point where our pin pierced the subregions, and
rebuild S. The points are indicated with black dots. Since the two points are
located in exactly th e same place with respect to the lattice lines, it now is possible to translate S (in the direction of the arrow), so that both white points lie
on lattice points, and we're done! _Problems and Exercises
3.3.10 Prove the intermediate pigeonhole principle,
using argument by contradiction.
3.3.11 Show that in any finite gathering of people,
there are at least two people who know the same num
ber of people at the gathering (assume that "knowing"
is a mutual relationship).
3.3.12 Use argument by contradiction to prove the fol
lowing useful variant of the pigeonhole principle: Let
al ,a 2 , ... ,an be positive integers. If
(al + a 2 + ... + an) - n + 1
pigeons are put into n pigeonholes, then for some i,
the statement "The ith pigeonhole contains at least ai
pigeons" must be tr ue.
3.3.13 Notice how simple the pigeonhole argument
was in Example 3. 3.2 on page 84. What is wrong with
the following "solution"?
Place four of the points on the vertices
of the square; that way they are maxi
mally separated from one another. Then
the fifth point must he within v'2/2 of
one of the other four points, for the fur
thest from the corners it could he would
be the center, and that is exactly v'2/2
units from each corner.3.3.14 Show that the decimal expansion of a rational
number must eventually become periodic.
3.3.15 Seven points are placed inside a regular
hexagon with side length 1. Show that at least two
points are at most one unit apart.
3.3.16 Inside a 1 x 1 square, 101 points are placed.
Show that some three of them form a triangle with area
no more than 0.01.
3.3.17 Show that among any n + 2 integers, either
there are two whose difference is a multiple of 2n, or
there are two whose sum is divisible by 2n.
3.3.18 Chose any (n + 1 )-element subset from
{I, 2, ... , 2n}. Show that this subset must contain two
integers that are relatively prime.
3.3.19 People are seated around a circular table at a
restaurant. The food is placed on a circular platform
in the center of the table, and this circular platform
can rotate (this is commonly found in Chinese restau
rants that specialize in banquets). Each person ordered
a different entree, and it turns out that no one has the
correct entree in front of him. Show that it is possible
to rotate the platform so that at least two people will
have the correct entree.
3.3.20 Consider a sequence of N positive integers