The Art and Craft of Problem Solving

52 CHAPTER 2 STRATEGIES FOR INVESTIGATING PROBLEMS

previous one, as follows. For each location in the grid,

examine that square, the square immediately above,

and the square immediately to the right. If there are

two or three grey squares among these three, then in

the next grid, color that location grey; otherwise. color

it white. Prove that after at most n steps all the squares

in the grid will be white.

Below is an example with n = 4. The first grid

shows the initial configuration, and the second grid

shows the configuration after one step.

2.3.36 Prove the conjecture that you made in Prob­

lem 2.2.20.

2.3.37 The Fibonacci sequence II '/ 2 ,13, ... was de­

fined in Example 1.3.18. In the problems below, prove

that each proposition holds for all positive integers 11.

(a) II + 13+ 15 + ... + 1211 - 1 = 1211 '

(b) 12 + 14 + ... + 1211 = 1211 + I -I.

(c) (^1) "<2".

(d) III = � { (I +

2 J5)" -(

I

- 2 J5),,}.

(e) If M is the matrix [ � ],

Mil = [ 111+^1 /,, ]

/" 1;,- 1

(f) In+t!n-I -!1 = (-1)".

(g) 1,;+ 1 + I'; = hll+ I.

then

2.3.38 If you did Problem 2.2.17 on page 37. you

probably discovered that if a triangle drawn on the co­

ordinate plane has vertices at lattice points, then

I

A= 2 B+J-1.

2.4 Other Important Strategies

where A. B and J respectively denote the area, number

of boundary lattice points and number of interior lat­

tice points of this triangle. This is a special case of

Pick's Theorem, which holds for any polygon with

vertices at lattice points (including non-convex poly­

gons). Prove Pick's Theorem with induction. Easy

version: assume that it is true for triangles (i.e., as­

sume the base case is true). Harder version: prove that

it is true for triangles first!

2.3.39 Here are a few questions about Example 2.3.9

on page 48, where we proved that the vertices of any

triangulation can be 3-colored so that no two adjacent

vertices are the same color.

(a) Our proof was "nonconstructive," in that it

showed that the coloring existed, but did not

show how 10 achieve it. Can you come up with a

"constructive" proof; i.e., can you outline a col­

oring algorithm that will work on an arbitrary

polygon?

(b) On page 49, we raised the question whether

any arbitrary triangulation of a polygon has a

"boundary triangle," i.e.. a triangle that cuts

the original polygon into two, rather than three,

pieces. It sure seems obvious. Prove it.

(c) In the diagram for the triangulation proof, the

"central" triangle split the polygon into two

parts, called L and R. What if the central tri­

angle had split the polygon into three parts?

2.3.40 Consider a 21999 x 21999 square. with a single

I x I square removed. Show that no matter where

the small square is removed. it is possible 10 tile this

"giant square minus tiny square" with ells (see Exam­

ple 1.3.19 on page 10 for another problem involving

tiling by ells).

2.3.4 1 (IMO 1997) An n x n matrix (square array)

whose entries come from the set S = {I. 2, ... , 2n-1 }

is called a silver matrix if, for each i = I ..... n. the ith

row and the ith column IOgether contain all the mem­

bers of S. Show that silver matrices exist for infinitely

many values of 11.

Many strategies can be applied at different stages of a problem, not just the beginning.

Here we focus on just a few powerful ideas. Learn to keep them in the back of your