The Art and Craft of Problem Solving

108 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS

asks intelligent questions!). If you cannot explain it to

his satisfaction, go back and reread the solution, mak­

ing note of the crux moves, auxiliary problems posed

and solved, etc. A solid understanding of this example

will help you with the next problem.

3.4.37 (lMO 1978) An international society has

its members from six different countries. The

list of members contains 1978 names, numbered

1 , 2 , ... ,1978. Prove that there is at least one mem­

ber whose number is the sum of the numbers of two

members from his own country, or twice as large as

the number of one member from his own country.

3.4.38 (lMO 1997) An n x n matrix (square array)

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

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

row and the ith column together contain all elements

of S. Show that there is no silver matrix for n = 1997.

3.4.39 (Taiwan 1995) Consider the operation which

transforms the 8-term sequence XI ,X2, ... ,Xg into the

new 8-term sequence

Find all 8-term sequences of integers that have the

property that after finitely many applications of this

operation, one is left with a sequence, all of whose

terms are equal.

3.4.40 Euler's Formula. Consider a polyhedron P.

We wish to show that v -e + / = 2, where v, e,j are

respectively the number of vertices, edges and faces

of P. Imagine that P is made of white rubber, with

the edges painted black and the vertices painted red.

Carefully cut out a face (but don't remove any edges

or vertices), and stretch the resulting object so that it

lies on a plane. For example, here is what a cube looks

like after such "surgery":

Now we want to prove that v -e + / = I for the new

object. To do so, start erasing edges and/or vertices,

one at a time. What does this do to the value of

v - e + /? What must you end up with?

3.4.41 If you haven't done Problem 2.4.24, now is the

time to take another look at it.

3.4.42 (Bay Area Mathematical Olympiad 2 (00) Al­

ice plays the following game of solitaire on a 20 x 20

chessboard. She begins by placing 100 pennies, 100

nickels, 100 dimes, and 100 quarters on the board so

that each of the 400 squares contains exactly one coin.

She then chooses 59 of these coins and removes them

from the board. After that, she removes coins, one at a

time, subject to the following rules:

• A penny may be removed only if there are four
  squares of the board adjacent to its square (up,
  down, left, and right) that are vacant (do not
  contain coins). Squares "off the board" do not
  count towards this four: for example, a non­
  comer square bordering the edge of the board
  has three adjacent squares, so a penny in such a
  square cannot be removed under this rule, even
  if all three adjacent squares are vacant.


• A nickel may be removed only if there are
  at least three vacant squares adjacent to its
  square. (And again, "off the board" squares
  do not count.)


• A dime may be removed only if there are at
  least two vacant squares adjacent to its square
  ("off the board" squares do not count).


• A quarter may be removed only if there is at
  least one vacant square adjacent to its square
  ("off the board" squares do not count).

Alice wins if she eventually succeeds in remov­

ing all the coins. Prove that it is impossible for her to

Win.