106 CHAPTER 3 TACTICS FOR SOLVING PROBLEMS
That, in fact, is where S came from in the first place! It was cleverly designed to make
the sum decrease when you move away from the goal, and not change when you move
toward it.
There is one more case: moves that leave the distance to C unchanged, such as,
for example, a jump from (1,4) to (-1,4). It is easy to check (do it!) that moves of
this kind decrease the Conway sum.
Thus the Conway sum is a monovariant that starts at a value of 1 and never in
creases. However, if a checker occupied C, its value would be SO = I, so the Conway
sum would be strictly greater than 1 (since other checkers must be on the board, and
S > 0). We conclude that it is not possible to reach C. •Problems and Exercises
3.4. 17 (Bay Area Mathematical Olympiad 2006) All
the chairs in a classroom are arranged in a square n x II
array (in other words, II columns and II rows), and ev
ery chair is occupied by a student. The teacher decides
to rearrange the students according to the following
two rules:- Every student must move to a new chair.
- A student can only move to an adjacent chair
in the same row or to an adjacent chair in the
same column. In other words, each student can
move only one chair horizontally or vertically.
(Note that the rules above allow two students in adja
cent chairs to exchange places.) Show that this proce
dure can be done if n is even. and cannot be done if n
is odd.
3.4. 18 An evil wizard has imprisoned 64 math geeks.
The wizard announces, "Tomorrow I will have you
stand in a line, and put a hat on each of your heads. The
hat will be colored either white or black. You will be
able to see the hats of everyone in front of you, but you
will not be able to see your hat or the hats of the peo
ple behind you. (You are not allowed to tum around.)
I will begin by asking the person at the back of the line
to guess his or her hat color. If the guess is correct,
that person will get a cookie. If the guess is wrong,
that person will be killed. Then I will ask the next per
son in line, and so on. You are only allowed to say the
single word 'black' or 'white' when it is your tum to
speak, and otherwise you are not allowed to commu
nicate with each other while you are standing in line.
Although you will not be able to see the people behind
you, you will know (by hearing) if they have answered
correctly or not."
The geeks are allowed to develop a strategy be
fore their ordeal begins. What is the largest number of
geeks that can be guaranteed to survive?
3.4. 19 Three frogs are placed on three vertices of a
square. Every minute, one frog leaps over another
frog, in such a way that the "leapee" is at the midpoint
of the line segment whose endpoints are the starting
and ending position of the "leaper." Will a frog ever
occupy the vertex of the square that was originally un
occupied?
3.4.20 Prove that if you add up the reciprocals of a se
quence of consecutive positive integers, the numerator
of the sum (in lowest terms) will always be odd. For
examp e, I '7^1 + 8 1 + 9 1 = 5ll4 '^191
3.4.21 (Bay Area Mathematical Olympiad 1999) A
lock has 16 keys arranged in a 4 x 4 array, each key
oriented either horizontally or vertically. In order to
open it, all the keys must be vertically oriented. When
a key is switched to another position, all the other keys
in the same row and column automatically switch their
positions too (see diagram). Show that no matter what
the starting positions are, it is always possible to open
this lock. (Only one key at a time can be switched.)II I I -I I I
- 1 -
3.4.22 Inspired by the Divisibility by Nine example