The Art and Craft of Problem Solving

92 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

containing n distinct integers. If N ;::: 2 n, show that

there is a consecutive block of integers whose product

is a perfect square. Is this inequality the best possible?

3.3.21 (Korea 1995) For any positive integer m, show

that there exist integers a, b satisfying

lal Sm, Ibl Sm,

3.3.22 Show that for any positive integer n, there ex­

ists a positive multiple of n that contains only the digits

7 and O.

3.3.23 To make sure that you understand Exam­

ple 3.3.7, explicitly construct the pigeonholes when

n = 25. Verify that the solution works in this case.

3.3.24 A chess player prepares for a tournament by

playing some practice games over a period of eight

weeks. She plays at least one game per day, but no

more than II games per week. Show that there must

be a period of consecutive days during which she plays

exactly 23 games.

3.3.25 (Putnam 1994) Prove that the points of an right

triangle of side length I cannot be colored in four col­

ors such that no two points at distance at least 2 -,;z

from each other receive the same color.

3.3.26 (Bay Area Mathematical Olympiad 2005 ) Let

n ;::: 12 be an integer, and let PI, P 2 , ... , Pn , Q be dis­

tinct points in the plane. Prove that for some i, at least

3.4 Invariants

n/6 - I of the distances

are less than Pi Q.

3.3.27 Example 3.3.5 on page 86 employed the pi­

geonhole principle several times in order to get a solu­

tion. There exists a fantasticalJy simple solution which

uses just one application of the (intermediate) pigeon­

hole principle. Can you find it?

3.3.28 The folJowing problems are inspired by the

very easy Example 3 .3.1. However, not aU of the vari­

ations below are easy. Have fun!

(a) Color the plane in three colors. Prove that there

are two points of the same color one unit apart.

(b) Color the plane in two colors. Prove that one

of these colors contains pairs of points at every

mutual distance.

(c) Color the plane in two colors. Prove that there

will always exist an equilateral triangle with aU

its vertices of the same color.

(d) Show that it is possible to color the plane in two

colors in such a way that there cannot exist an

equilateral triangle of side I with aU vertices the

same color.

(e) Color the plane in two colors. Show that there

exists a rectangle aU of whose vertices are the

same color.

Our discussion of the extreme principle mentioned the importance of extracting key

information from the chaos that most problems initially present. The strategy is some­

how to "reduce" the problem so as to focus on certain essential entities. In Section 3.2,

the tactic to implement this strategy was to focus on extreme values. There are other

tactics with the same underlying strategy. Here we shall introduce the very rich topic

of invariants.

An invariant, as the name suggests, is merely some aspect of a problem-usually

a numerical quantity-that does not change, even if many other properties do change.

Here are a few examples.

Example 3.4. 1 The Motel Room Paradox. Recall Example 2. 1.8 on page 20, the prob­

lem involving three women who check into a motel room. Let g, p,d be the amount

the guests spent, the amount the porter pocketed for himself and the amount the motel

desk received, respectively. Then the quantity

g-p-d