(b) Prove that it is impossible to find a tiling of
the plane with infinitely many unit squares and
finitely many (and at least one) unit equilateral
triangles in the same tiling.3.2.10 Suppose you are given a finite set of coins in
the plane, all with different diameters. Show that one
of the coins is tangent to at most five of the others.
3.2.11 Fix the proof in Example 2.3.5 on page 45.
Show that even a concave polygon has an acute an
gle that we can use to "snip off' a triangle. Why do we
need the extreme principle for this?
3.2.12 (Canada 19 87) On a large, flat field, n people
(n > I) are positioned so that for each person the dis
tances to all the other people are different. Each person
holds a water pistol and at a given signal fires and hits
the person who is closest. When n is odd, show that
there is at least one person left dry. Is this always true
when n is even?
3.2.13 Our solution to the GCD-LCM problem (Ex
ample 3.2.4 on page 77) omitted a proof that the se
quence eventually forms a chain where each element
divides the next (when arranged in increasing order).
Modify the argument to do this (if you understand the
original argument, you should be able to do this with
just a tiny bit of work).
3.2.14 (Russia 1996) A palindrome is a number or
word that is the same when read forward and back
ward, for example, "176671" and "civic." Can the
number obtained by writing the numbers from I to n
in order (for some n > I) be a palindrome?
3.2.15 Place the integers 1,2,3, ... , n^2 (without dupli
cation) in any order onto an n x n chessboard, with
one integer per square. Show that there exist two ad
jacent entries whose difference is at least n + I. (Ad
jacent means horizontally or vertically or diagonally
adjacent.)
3.2.16 After experimenting with Problem 2.1.26 on
page 24, you probably have come to the conclusion
that the only possible configurations are those where
the degree of each crossing point (i.e., number of lines
emanating from the crossing point) is even or those
where exactly two crossing points have odd degree,
and in this latter case, the path must begin at one of
the odd-degree points and end at the other one. Now
3.2 THE EXTREME PRINCIPLE 83you are ready to prove this conjecture. Use an extremal
argument. Consider the longest "legal" path and try to
argue (by contradiction) that this path includes all the
lines in your figure.
3.2.17 The extreme principle in numher theory. In Ex
ample 3.2. 4 on page 77, we encountered the notions of
greatest common divisor and least common multiple.
Here we mention another simple number theory idea,
the division algorithm:
Let a and h he positive integers. h 2 a.
Then there exist integers q, r satisfying
q 2 I and 0 S r < a sueh that
h = qa +r.
In other words, if you divide h by a, you get a positive
integer quotient q with a remainder r that is at least
zero (equals zero if alh) but smaller than a. The divi
sion algorithm is an "obvious" idea, one that you have
seen since grade school. It is actually a consequence
of the well-ordering principle.
(a) As a warm-up, prove the division algorithm
rigorously, by considering the minimum non
negative value of h -at as t ranges through the
positive integers.
(b) Another warm-up: prove (this should take two
seconds!) that if alh and ale, then al(hx+cy)
for any integers x,y (positive or negative).
(c) Now show that if aim and him, then
LCM(a,h) lm.
(d) Finally, show that for any integers a.h, the
greatest common divisor of a and h is equal
to the minimum value of ax + hy, as x and y
range through all integers (positive and nega
tive). For example, if a = 7, h = II, we have
GCD(7, II) = I (since 7 and II are primes, they
share no common divisors except I), but also
1=(-3)·7+2·11.
3.2.18 Let P(x) = anx" + an_lx"- 1 + ... + a() be a
polynomial with integer coefficients and let q be a
prime. If q is a factor of each of all- I. all-2 ..... al • a(),
but q is not a factor of all, and q^2 is not a factor of a(),
then P(x) is irreducible over the rationals; i.e., P(�\)
cannot be factored into two non-constant polynomials
with rational coefficients.