Solutions and Comments
Because of space limitations, the solutions below will often be
abbreviated and you are encouraged to fill in the details
yourself. Part of the art of writing up a solutions is to
know what details to cover and which can be passed over
quickly. Basically, each step that is
not completely standard should justified or at least
provided with a cue that will remind the reader of a
suitable background result. In recording manipulations,
you do not have to put in each step but you should indicate
at key points what the reader must do to reproduce the
calculation. Remember: if the
marker has not got a clue what you are up to, even after
much reflection, you will not get the mark. There are two
stages to solving a problem: (a) figuring out what the
solution is; (b) writing it up. The order in which the
ideas occur in attaining (a) is not always the best order
for implementing (b), and you should regard (a) and (b)
as separate processes. This means that you may have to
refine your ideas and reorganize your material.
- 1.
-
Let M be a set of eleven points consisting of the four
vertices along with seven interior points of a square of unit area.
-
-
(a) Prove that there are three of these points that are
vertices of a triangle whose area is at most 1/16.
-
-
(b) Give an example of a set M for which no four of
the interior points are collinear and each nondegenerate triangle
formed by three of them has area at least 1/16.
Solution. (a) We begin by covering the square with non-overlapping
triangles whose vertices are found among the eleven points. Begin by
drawing one of the diagonals of the square. We then select the remaining
seven points in turn. Suppose, as an induction hypothesis, that we have
selected k ³ 0 points and covered the square with 2(k + 1) triangles
whose vertices are among the four vertices of the square and the k
points already selected. Consider the next point. If it is in the interior
of an existing triangle, join it to each of the three vertices of the
triangle. If it is in the interior of an edge common to two triangles,
join it to the remaining vertex of each of the triangles. In each case,
we have two more triangles than before,
for a total of 2(k + 3) triangles.
When all seven interior points have been selected, we have a total of
2 ×8 = 16 triangles. The total area of these sixteen nonoverlapping
triangles is 1, so at least one of them must have area not exceeding 1/16.
(b) Let the square have vertices at (0, 0), (1, 0), (0, 1), (1, 1) and
let the interior points be at (1/8, 5/8),
(2/8, 2/8), (3/8, 7/8), (4/8,4/8), (5/8, 1/8), (6/8. 6/8)
and (7/8, 3/8). There is a triangulation for which each
of the triangles has area exactly equal to 1/16. (Exercise: produce the
diagram.) Any other triangle determined by three of the points will have
area at least as large as some triangle in the triangulation.
Comment. (a) Most students realized that one had only to look at the
triangles involved in some triangulation of the square. There are two issues
that need to be addressed: that such a triangulation exists, and the
number of triangles obtained. This was neglected by some solvers.
The induction argument above looks after both of these issues. Given that
there is a triangulation, the number of triangles can be counted in another way.
Suppose that there are N triangles. Then the total of all of the angles
of the triangles is 2N right angles. The angles of the triangles
at each corner points of the square total to one right angle, while at the
interior seven points of the square total to four right angles, for a total
of 4 + 4×7 = 32 right angles. Since 32 = 2N, there are 16 triangles.
(b) Most people did not produce an example. The ones who did either transgressed
the condition about not having too many collinear points, or else did not ensure
that the area of every triangle, even those not involved in the triangulation,
was at least 1/16.
- 2.
-
Let a, b, c be the lengths of the sides of a
triangle. Suppose that u = a2 + b2 + c2 and v = (a + b + c)2.
Prove that
and that the fraction 1/2 on the right cannot be replaced by a smaller
number.
Solution. The numerator of the difference 1/2 - u/v
is equal to
|
| |
|
|
= 2(ab + bc + ca) - (a2 + b2 + c2) |
| |
| = a(b + c - a) + b(c + a - b) + c(a + b - c) . |
|
| |
|
By the triangle inequality, a < b + c, b < c + a and c < a + b,
so that the right side is always positive. Since all variables are
positive, the right inequality follows.
The numerator of u/v - 1/3 is equal to
|
| |
|
|
= 2(a2 + b2 + c2 - ab - bc - ca) |
| |
| = (a - b)2 + (b - c)2 + (c - a)2 , |
|
| |
|
The right side, being a sum of squares, is nonnegative and it
vanishes if and only if a = b = c. The left inequality follows.
To see that u/v can be arbitrarily close to 1/2, let
(a, b, c) = (e, 1, 1) where 0 < e < 4. Then
|
|
1
2
|
- |
u
v
|
= |
e(4 - e)
(2 + e)2
|
. |
|
This can be made as close to 0 as desired by taking e
sufficiently close to 0.
Coment. The inequality v £ 3u can be obtained by
applying the Cauchy-Schwarz Inequality (try it!).
Robert Barrington Leight found it convenient to look
at the reciprocal v/u. In showing that this could be
as close as desired to 1/2, note that, when
(a, b, c) = (e, 1, 1),
|
2 < |
v
u
|
= 1 + |
2(ab + bc + ca)
a2 + b2 + c2
|
= 1 + |
4 e+ 2
e+ 2
|
< 1 + |
4e+ 2
2
|
= 2 + 2e . |
|
Some students tried to argue the inequality by
looking at extreme situations, without attempting to draw a
relationship between the extreme and general situations.
Others tried a kind of variation argument, seeming to feel that
since we can change the variables to a situation where the
inequality holds, it will hold on the way there. While it is
often useful to think in terms of extreme cases and variation
of the unknowns in an inequality problem in order to get a handle
on the situation, this approach generally becomes completely
unmanageable in the write-up. It is best to think of the
variables as being fixed at certain values and perhaps try to
compare the value of a function to a purported extreme value.
In many inequalities, including this
one, it is often conceptually cleanest to look at the difference
between two sides; this difference can usually be manipulated into
a form which is clearly positive or negative, in a way in which
the reader can easily follow the steps. If you ever depart from
this format, you should have a good reason for doing so.
Avoid in the write-up
starting with what you have to prove and working backwards; this
makes the logic harder to follow and
could lead to trouble with steps that are not reversible.
Begin with what you know and proceed
by logical steps to what has to be obtained.
- 3.
-
Suppose that f(x) is a function satisfying
for all positive rational numbers n and m. Show that, for all
natural numbers k,
|
|
k
å
i = 1
|
|f(2k) - f(2i) | £ |
k(k-1)
2
|
. |
|
Solution. Taking the case m = n = 2i, we find that
for each nonnegative integer i. Hence
|
|f(2k) - f(2i) | £ |f(2k) - f(2k-1) |+ |f(2k-1) + f(2k-2) |+ ¼+ |f(2i+1 - f(2i) | £ k - i . |
|
so that
|
|
k
å
i = 1
|
|f(2k) - f(2i) | £ |
k
å
i = 1
|
(k - i) = |
k-1
å
j = 0
|
j = |
k(k-1)
2
|
. |
|
Comment. One student picked up that the condition does
not make sense when m/n is negative, so I have corrected
the statement of the problem. Others (including myself) either
rolled with the context or corrected the statement to something
reasonable. It does happen that a problem can be misstated
on a competition; if you feel that this has happened, you
should draw attention to the mistake and make a reasonable
nontrivial interpretation of the problem and solve that.
This problem provided a nice illustration of the maxim that
a little knowledge is a dangerous
thing. Students who had seen some calculus thought that somehow a
derivative was involved, and then were lost forever beneath the waves.
The context does not suggest a place for calculus. Calculus
deals with functions defined on the real numbers (not just the
rationals) and possessing derivatives. The most important thing
for you to
learn about calculus is when not to use it. More seriously, turning
to calculus right off the bat inhibits the ability to take the
problem on its own terms and come up with a more elementary solution.
Resist the urge to categorize problems too quickly. Once the key idea
of looking at consecutive powers of 2 is found, the solution then falls
right out.
- 4.
-
Is it true that any pair of triangles sharing a common angle,
inradius and circumradius must be congruent?
Solution. Let ABC be the triangle, with sides a, b, c,
circumradius R, inradius r, semiperimeter s, area
D and u, v, w the respective lengths
of the tangents to the incircle from vertices A, B, C. We are given
that angle A, and radii r and R are fixed. Then also fixed are
a = 2R sinA, b + c - a = u = r cotA/2, b + c = u + a,
s = (u + 2a)/2 and D = rs. But
D = 1/2bc sinA, so we find that bc and b + c are
both fixed. Now b and c are the uniquely determined roots
of a quadratic equation (whose coefficients are fixed by the sum and
product of the roots), and the result follows.
Comment. There is a natural dynamical way of
looking at the situation which is hard to capture in a
rigorous argument. We can imagine
a fixed circumcircle with A fixed as one point on its circumference.
Let the angle at A be fixed, but let its arms vary within the
circumcircle. Since we know the radius of the incircle enveloped
by the arms, this incircle is a fixed distance from A (why?);
as we move the arms around, we can convince ourselves that there are
two positions (giving congruent triangles) where the incircle will
be tangent to the chord of the circumcircle determined by the arms of
the angle at A. Nailing all this down is not so easy, and seems to need
at the least a continuity argument, which takes us out of the realm
of pure geometry into that of analysis.
- 5.
-
Each point of the plane is coloured with one of 2000 different
colours. Prove that there exists a rectangle all of whose vertices have
the same colour.
Solution. Let N = 1000 and let S consist of points
(x, y) with integer coordinates for which
0 £ x £ N, 0 £ y. Each row
Ry : = { (x, y) Î S: 0 £ x £ N } has N + 1 points, so that
by the Pigeonhole Principle, there is at least one colour used twice.
There are N ((N + 1) || 2) possible ways in which a colour can be used
in two positions on Ry. Since there are more than this many rows
Ry, the same colour must occur in the same two positions
in two of these rows. The four points
in these two positions on the two rows determine the desired rectangle.
Comment. Many students essentially had this pigeonhole
argument, which was set up in a variety of ways.
- 6.
-
Let n be a positive integer, P be a set of n primes and
M a set of at least n+1 natural numbers, each of which is divisible
by no primes other than those belonging to P. Prove that there is
a nonvoid subset of M, the product of whose elements is a square
integer.
Solution. Let P consist of the distinct
primes p1, p2, ¼, pn.
Let S be a nonvoid subset of M, and write the
product of the numbers in S in the form
x = y2 z, where y2 is the largest square divisor of
x. Then z must have the form
where the vector (a1, a2, ¼, an) has all of its
entries equal to either 0 or 1. There are 2n possibilities for
this vector. However, there are
at least 2n+1 - 1 > 2n nonvoid subsets of
M and so that many possible products x. Hence there are
two such products, x = y2 z and u = v2 w which give rise to
the same vector. It may transpire that both x and u have factors
from M in common; divide through by the product of these factors
to obtain products of disjoint subsets P and Q of M. These two products
will have the same vector, and so must have the form
r2 t and s2 t, where t is a product of distinct primes from
P. The product of the numbers in P ÈQ is r2 s2 t2, and this
is the desired square.
