The Art and Craft of Problem Solving

90 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS

The above problem was mathematically very sophisticated, and not just because

it used linear algebra. Two other new ideas used were

• A quadratic polynomial P(x) cannot assume the same value for three differ­
  ent values of x. This is really an application of the Fundamental Theorem of
  Algebra (see Chapter 5).


• The define a function tool, which is part of a larger idea, the strategy of gener­
  alizing the scope of a problem before attacking it.
  We conclude with a lovely argument that includes, among other neat ideas, an
  application of the pigeonhole principle to an infinite set. Please take some time to
  think about the problem before reading its solution.

Example 3.3.9 Let S be a region in the plane (not necessarily convex) with area

greater than the positive integer n. Show that it is possible to translate S (i.e., slide

without turning or distorting) so that S covers at least n + 1 lattice points.

Solution: Here is an example. The region S has area 1.36 units. At first, S covers

just one lattice point, but it is possible to translate it down and to the right so that it

covers two lattice points.

...

·4' "

.·. ... .. ... .. ...... -.....

·

.

.

..
: :�:. :
: ..... · :. Z(f: .... : ..... :
·......
·......
.

.

·....

..

How do we develop a general argument? We will invent an algorithm that we

will apply to our example region S which will work for any region. Our algorithm has

several steps.

:'?f".: .. �:

: ·. b. :.

· · c....

:···d·: � ... :

· ·....

·..

2

·..

.

?f

a

.

: ·. " ". b·· :.

· · c....

:. ···d· : e"�

·..

·..

·..

3

I. First, take S and decompose it into finitely many subregions, each lying on its

own lattice square. In our example, S breaks up into the five regions a, h, c, d, e.