on page 94, discover and prove a similar statement for
divisibility by II.3.4.23 Start with a set of lattice points. Each second,
we can perform one of the following operations;
I. The point (x,y) "gives birth" to the point (x +
I,y+ I).
- If x and y are both even, the point (x,y) "gives
birth" to the point (x/2,y/2). - The pair of points (x,y) and (y,z) "gives birth"
to (x,z).
For example, if we started with the single point (9, I),
operation #1 yields the new point (10,2), and then op
eration #2 yields (5, I), and then nine applications of
operation #1 give us (14, 10), and then operation #3
applied to (14, 10) and (10,2) gives us (14,2), etc.
If we start with the single point (7,29), is it pos
sible eventually to get the point (3, 1999)?
3.4.24 Initially, we are given the sequence
1,2, ... , 100. Every minute, we erase any two num
bers u and v and replace them with the value uv + u + v.
Clearly, we will be left with just one number after 99
minutes. Does this number depend on the choices that
we made?
3.4.25 Prove that it is impossible to choose three dis
tinct integers a,b and c such that
(a-b)l(b-c), (b-c)l(c-a), (c-a)l(a-b).
3.4.26 (Tom Rike) Start with the set {3,4, 12}. You
are then allowed to replace any two numbers a and b
with the new pair 0.6a -0.8b and 0.8a + 0.6b. Can
you transform the set into {4,6, 12}?
3.4.27 Two people take turns cutting up a rectangu
lar chocolate bar that is 6 x 8 squares in size. You are
allowed to cut the bar only along a division between
the squares and your cut can be only a straight line.
For example, you can tum the original bar into a 6 x 2
piece and a 6 x 6 piece, and this latter piece can be
turned into a I x 6 piece and a 5 x 6 piece. The last
player who can break the chocolate wins (and gets to
eat the chocolate bar). Is there a winning strategy for
the first or second player? What about the general case
(the starting bar is m x n)?
3.4.28 Consider a row of 2n squares colored alter
nately black and white. A legal move consists of
choosing any contiguous set of squares (one or more
squares, but if you pick more than one square your
squares must be next to one another; i.e., no "gaps"
3.4 INVARIANTS 107allowed), and inverting their colors. What is the mini
mum number of moves required to make the entire row
be one color? Clearly, n moves will work (for exam
ple, invert the 1st square, then the 3rd square, etc.), but
can you do better than that?
3.4.29 Answer the same question as above, except
now start with a 2n x 2n "checkerboard" and a legal
move consists of choosing any subrectangle and in
verting its colors.
3.4.30 Show that if every room in a house has an even
number of doors, then the number of outside entrance
doors must be even as well.
3.4.31 Twenty-three people, each with integral
weight, decide to play football, separating into two
teams of II people, plus a referee. To keep things fair,
the teams chosen must have equal total weight. It turns
out that no matter who is chosen to be the referee, this
can always be done. Prove that the 23 people must all
have the same weight.
3.4.32 (Russia 1995) There are n seats on a merry
go-round. A boy takes n rides. Between each ride,
he moves clockwise a certain number of places to a
new horse. Each time he moves a different number of
places. Find all n for which the boy ends up riding
each horse.
3.4.33 Consider nine lattice points in three
dimensional space. Show that there must be a lattice
point on the interior of one of the line segments joining
two of these points.
3.4.34 The first six terms of a sequence are
o 1 2 3 4 5 Each subsequent term is the last digit
of the'
s�� �f the six previous terms. In other words,
the seventh term is 5 (since 0 + I + 2 + 3 + 4 + 5 = 15),
the eighth term is 0 (since I + 2 + 3 + 4 + 5 + 5 = 20),
etc. Can the subsequence 13579 occur anywhere in
this sequence?
3.4.35 The solution to the checker problem (Exam
ple 3.4.16) was rather slick, and almost seemed like
cheating. Why couldn't you assign any value that you
wanted to the point C, for example, IOIOO? Then this
would assure that you could never get there. What is
wrong with this idea?
3.4.36 Make sure that you really understand how Ex
ample 3.4.10 works. For example, exactly how many
times is the pigeonhole principle used in this problem?
After reading the solution, see how well you can ex
plain this problem to another person (someone who