!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "DTD/xhtml1-transitional.dtd"> Solutions and Comments

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.

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 k0 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.

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

1 3 u v < 1 2

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

v-2u =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

3u-v =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)=(ε,1,1) where 0<ε<4. Then

1 2 - u v = ε(4-ε) (2+ε)2 .

This can be made as close to 0 as desired by taking ε sufficiently close to 0.
Coment. The inequality v3u 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)=(ε,1,1),

2< v u =1+ 2(ab+bc+ca) a2 + b2 + c2 =1+ 4ε+2 ε+2 <1+ 4ε+2 2 =2+2ε.

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.

Suppose that f(x) is a function satisfying

f(m+n)-f(m) n m

for all positive rational numbers n and m. Show that, for all natural numbers k,

i=1 kf( 2k )-f( 2i ) k(k-1) 2 .

Solution. Taking the case m=n= 2i , we find that

f( 2i+1 )-f( 2i )1

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

i=1 kf( 2k )-f( 2i ) i=1 k(k-i)= j=0 k-1j= 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.

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 Δ 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=2RsinA, b+c-a=u=rcot A 2 , b+c=u+a, s=(u+2a)/2 and Δ=rs. But Δ= 1 2 bcsinA, 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.

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 0xN,0y. Each row Ry :={(x,y)S:0xN} 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.

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

p1 a1 p2 a2 pn an

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 PQ is r2 s2 t2 , and this is the desired square.