The Art and Craft of Problem Solving

82 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS

is less than or equal to n. Let's pick al + a6. If this sum is less than or equal to n,

goodness implies that one of the ak is equal to al + a6. But this is impossible, because

the ai are positive and monotone. A contradiction!

Now try assuming that a2 + as ::; n. Then this sum equals ak for some k between

I and 6. This sum is strictly greater than as, so we must have a2 + as = a6. So far,

no contradiction. But we have not exhausted the hypotheses of goodness. The sum

al +as is strictly less than a2 +as (by monotonicity); hence al +as = aj for some j

between I and 6. But aj > as, which forces aj = a6. But this can't be, since al +as is

strictly less than a2 + as = a6, since all terms are distinct. Another contradiction.

Likewise, if we assume that a3 + a4 ::; n, goodness will imply that a3 + a4 equals

either as or a6. But the sums al + a4 and a2 + a4 are also::; n, and greater than a4, and

distinct. But this is a contradiction: we have three distinct sums (a3 + a4,a2 + a4, and

al +a4) with only two possible values (as and a6).

Finally, we can produce a general argument. Before you read it, try to write it up

on your own. The following argument assumes that n is even. You will need to alter it

slightly for the case where n is odd.

Let ai, a2, ... , am be good, and without loss of generality assume that

We will prove that al + a2 + ... + am 2 m(n + 1) 12 by showing the stronger result that

each of the pairs al +an,a2 +an-l, ... an/ 2 ,an/ (^2) + 1 is greater than or equal to n+ 1.
Assume not. Then for some j ::; n12, we must have a j + an-j ::; n. Goodness implies

that for some k, 1 ::; k ::; m, we have a j + an-j = ak. In fact, k > n -j, because the

terms are positive and the sequence is monotone increasing. Likewise, each of the j

sums

al +an-j,a2 +an-j,··· ,aj,an-j

is less than or equal to n and distinct, and each greater than an-j. Goodness implies

that each of these sums is equal to at for some I > n -j. There are only j - 1 choices

for I, but there are j different sums. We have achieved our contradiction. _

Problems and Exercises

3.2.7 Imagine an infinite chessboard that contains a

positive integer in each square. If the value in each

square is equal to the average of its four neighbors to

the north, south, west, and east, prove the values in all

the squares are equal.

3.2.8 There are 2000 points on a circle, and each point

is given a number that is equal to the average of the

numbers of its two nearest neighbors. Show that all

the numbers must be equal.

3.2.9 (Bay Area Mathematical Olympiad 2004) A

tiling of the plane with polygons consists of placing

the polygons in the plane so that interiors of polygons

do not overlap, each vertex of one polygon coincides

with a vertex of another polygon, and no point of the

plane is left uncovered. A unit polygon is a polygon

with all sides of length one.

Il is quite easy to tile the plane with infinitely

many unit squares. Likewise, it is easy to tile the plane

with infinitely many unit equilateral triangles.

(a) Prove that there is a tiling of the plane with in­

finitely many unit squares and infinitely many

unit equilateral triangles in the same tiling.