A1. n is a positive integer. Show that zn+1 - zn - 1 = 0 has a root on the unit circle |z| = 1 iff n is congruent to 4 mod 6.
A2. An equilateral triangle side n is divided into n2 equilateral triangles of side 1 by lines parallel to its sides. The n(n+1)/2 vertices of the triangles are each labeled with a real number, so that if ABC and BCD are small triangles then the sum of the labels on A and D equals the sum of the labels on B and C. The labels on the vertices of the original triangle are a, b and c. What is the shortest distance between a vertex with the largest label and a vertex with the smallest label? What is the sum of all the labels?
A3. In a tournament each player plays every other player. Every game results in win or loss. A prize is awarded to every player X who fulfils the following condition: for each player Z who beats X there must be a player Y such that X beats Y and Y beats Z. Only one prize is awarded. Show that the recipient must have won every game.
B1. Given five points inside an equilateral triangle of area 1, show that one can find three equilateral triangles with total area at most 0.64 and sides parallel to the original triangle, so that each of the five points is inside one or more of the new triangles.
B2. A tetrahedron has the following properties. There is a sphere, center X, which touches each edge of the tetrahedron; there are four spheres with centers the vertices of the tetrahedron which each touch each other externally; and there is another sphere center X which touches all four spheres. Prove that the tetrahedron is regular.
B3. A set of distinct positive integers has sum 1987. What is the maximum possible value for three times the total number of integers plus the number of odd integers?
Solutions
Problem A1
n is a positive integer. Show that zn+1 - zn - 1 = 0 has a root on the unit circle |z| = 1 iff n is congruent to 4 mod 6.
Solution
If z is a root, we have zn(z - 1) = 1. Hence if also |z| = 1, then |z - 1| = 1. So 0, 1, z must form the vertices of an equilateral triangle. Hence z = exp(± i π/3), so that (z - 1) = exp(± 2iπ/3). But zn(z - 1) = 1, so n+2 must be a multiple of 6 and it is easy to see that this is also a sufficient condition.
Problem A2
An equilateral triangle side n is divided into n2 equilateral triangles of side 1 by lines parallel to its sides. The n(n+1)/2 vertices of the triangles are each labeled with a real number, so that if ABC and BCD are small triangles then the sum of the labels on A and D equals the sum of the labels on B and C. The labels on the vertices of the original triangle are a, b and c. What is the shortest distance between a vertex with the largest label and a vertex with the smallest label? What is the sum of all the labels?
Solution
Take any three adjacent small triangles ABC, BCD, BDE. wlog the labels on A, B, C are d, d+x, d+y. Then the label on D must be d+x+y and the label on E must be d+2x. It is now an easy induction to show that the vertices along the line DBE are an arithmetic progression with difference x. Another induction shows that the labels along any line of vertices parallel to DBE is also an arithmetic progression with the same difference. If the two vertices of the large triangle along such a line have labels a and b, then we see that x must be (b - a)/n. Similarly, the vertices along a line parallel to the side a c must have labels in arithmetic progression with difference (a - c)/n, and vertices along a line in the third direction are in arithmetic progression with difference (c - b)/n. If all a, b, c are distinct, then it follows that the smallest and largest values must occur at the three vertices of the large triangle and hence their distance apart must be n. If just two are distinct, then one extreme value occurs just at a vertex of the large triangle and the other occurs at all vertices along the opposite side. So the shortest distance is n (√3)/2 for n even and √(1/4 + 3n2/4) for n odd. If a = b = c, then all the vertices have the same label and so the shortest distance is 1 (or 0 according to taste).
The sum of the vertices along the side from a to b is (n + 1)(a + b)/2. Similarly, for the other two sides, so the sum around the perimeter is n(a + b + c) = no. of points x (a + b + c)/2. If a = b + nx, b = c + ny, then the vertices of the large triangle formed by the remaining points have labels a - 2x - y, b + x - y, c + x + 2y, so the sum around the perimeter is again (no. of points) x (a + b + c)/2. Thus the sum of all the labels = no. of points x (a + b + c)/3 = (1 + 2 + ... + n+1)(a + b + c)/3 = (n + 1)(n + 2)(a + b + c)/6.
Problem A3
In a tournament each player plays every other player. Every game results in win or loss. A prize is awarded to every player X who fulfils the following condition: for each player Z who beats X there must be a player Y such that X beats Y and Y beats Z. Only one prize is awarded. Show that the recipient must have won every game.
Solution
We show first that if no player has a higher score than X, then X fulfils the condition. For suppose no player has a higher score than X. If Y beats X, and beats everyone whom X beats, then X has a lower score than Y contradiction. So if Y beats X, then there must be someone whom X beats who beats Y, so X fulfils the condition.
Suppose A receives the only prize. Let S be the set of players who beat A. Let B have the highest score from the games between players in S. Then we have just shown that given any other player C in S, B either beats C or beat someone who beat C. But B also beat A who beat everyone outside S. So B is eligible for a prize. Contradiction. So S must be empty.
Problem B1
Given five points inside an equilateral triangle of area 1, show that one can find three equilateral triangles with total area at most 0.64 and sides parallel to the original triangle, so that each of the five points is inside one or more of the new triangles.
Solution
Divide the triangle into 25 triangles area 1/25 by lines parallel to its sides. If 3 points lie inside one of the three triangles made up of 16 small triangles (and area 0.64), then we can cover the other two with triangles of zero area. So we can assume that at least 3 points lie inside the 9 triangles along each side. That means there are two possibilities: (1) two corner parallelograms (each made up of two small triangles) each contain 2 points and the 5th point is in the other corner parallelogram; or (2) one corner parallelogram contains 2 points, two contain 1 each and the 5th point lies in the five small triangles lying between them. In case (1) we can take a triangle area 4/25 containing each corner parallelogram (total area 0.48). In case (2) we can take a triangle area 9/25 containing the point on the side and the nearest corner parallelogram, a small triangle area 1/25 containing the other single corner point and a triangle area 4/25 containing the corner parallelogram with two points (total area 0.56).
Problem B2
A tetrahedron has the following properties. There is a sphere, center X, which touches each edge of the tetrahedron; there are four spheres with centers the vertices of the tetrahedron which each touch each other externally; and there is another sphere center X which touches all four spheres. Prove that the tetrahedron is regular.
Solution
Let AB be a side of the tetrahedron. Let the spheres center A and B touch at R on AB, and let the sphere center X touch AB at W. The key insight is that R = W.
Let C be another vertex of the tetrahedron. Suppose the vertex spheres meet at U on BC and V on CA. Then AV = AW, BU = BW, CU = CV, so AB = AV + CU, BC = BU + CU, CA = CU + AV, so AV + BU + CU = (AB + BC + CA)/2, so AV = (AB - BC + CA)/2, BU = (AB + BC - CA)/2, CU = (-AB + BC + CA)/2.
Suppose the sphere center X touches BC at P and CA at Q. Then AR and AQ are tangents to the sphere center X, so they are equal. Similarly, BP = BR, CP = CQ. So exactly the same argument as above shows that AQ = (AB - BC + CA)/2 etc. Hence the points coincide: P = U, Q = V, R = W.
Now consider the right-angled triangle XAR. We have AX2 = AR2 + XR2. Suppose the sphere center X touching the vertex spheres has radius R and the sphere center X touching the sides has radius r. If the sphere radius R encloses one of the vertex spheres then it must enclose them all (since they touch at a different point). So either XA = R + AR (and similarly for XB, XC, XD) or XA = R - AR (and similarly for XB etc). Hence R2 ± 2R AR + AR2 = AR2 + r2, so AR = ± (R2 - r2)/R. Similarly for BR, CP etc with the same sign in all cases. Hence all the sides have the same length and the tetrahedron is regular.
Problem B3
A set of distinct positive integers has sum 1987. What is the maximum possible value for three times the total number of integers plus the number of odd integers?
Solution
1 + 2 + ... + 62 = 62·63/2 = 1953, 1 + 2 + ... + 63 = 63·64/2 = 2016. So we can find at most 62 distinct integers with sum 1987. We can take 35 of these to be odd and 27 even without penalty: 1 + 2 + ... + 54 (so far 27 of each) + 55 + 57 + 59 + 61 + 63 + 65 + 67 + 69 = 1981. But if we increase the number of odd any further we must decrease the total number (replacing 54 by 71 is an increase of 17). If we replace 4 even numbers we cannot replace them by 3 odd numbers (71 + 73 + 75 - 54 - 52 - 50 - 48 = 15 > 6). So this is the best we can do. To get a total actually equal to 1987 just increase one of the odd numbers by 6, eg 75 instead of 69. That gives 4·35 + 3·27 = 221.
The argument that 221 is optimal is perhaps not entirely convincing. So suppose we have m odd numbers and n even numbers. The total of the odd numbers cannot be less than the sum of the first m odd numbers which is m2 and the sum of the even numbers cannot be less than the sum of the first n even numbers which is n(n+1). So we must show that if 4m + 3n >= 222, then m2 + n(n+1) > 1987. But 4m + 3n ≥ 222 implies 4m + 3(n + 1/2) ≥ 223 1/2 and hence, by Cauchy-Schwartz, 5√(m2 + (n+ 1/2)2) > 223 1/2, so m2 + n2 + n > (447/10)2 - 1/4 > 1987.
Labels:
Chinese Mathematical Olympiad
Previous Article
