6th Australian Mathematical Olympiad Problems 1985

A1.  Find the sum of the first n terms of 0, 1, 1, 2, 2, 3, 3, 4, 4, ... (each positive integer occurs twice). Show that the sum of the first m + n terms is mn larger than the sum of the first m - n terms.

A2.  Show that any real values satisfying x + y + z = 5, xy + yz + zx = 3 lie between -1 and 13/3.

A3.  A graph has 9 points and 36 edges. Each edge is colored red or black, so that every triangle has at least one red side. Show that there are four points with all edges between them red.

B1.  A triangle ABC has all angles smaller than 120^o. An equilateral triangle is constructed on the outside of each side by constructing three new vertices D, E, F. Show that the three lines joining the new vertex of each equilateral triangle to the opposite vertex of ABC meet at a point X. Show that XD + XE + XF = 2(XA + XB + XC).

B2.  Find all possible positive integers which have at least seven positive divisors and equal one less than the sum of the squares of their sixth and seventh divisors, when the divisors are listed in order of increasing size.

B3.  Find all real polynomials p(x) such that p(x² + x + 1) = p(x) p(x + 1). 

Solutions

Problem A1

Find the sum of the first n terms of 0, 1, 1, 2, 2, 3, 3, 4, 4, ... (each positive integer occurs twice). Show that the sum of the first m + n terms is mn larger than the sum of the first m - n terms.

Answer

n²/4 for n even, (n²-1)/4 for n odd. One could also express that as [n²/4] for all n.

Solution

We know that 1 + 2 + ... + n = n(n+1)/2 (reverse the order and add and we get n pairs of terms with sum n+1 each). So the sum of the first 2n+1 terms is n(n+1). The sum of the first 2n terms is n less or n². Suppose m+n is even. Then m-n is also even, so the sum of the first m+n less the sum of the first m-n is ¼(m+n)² - ¼(m-n)² = mn. Similarly, if m+n is odd, the difference is ¼(m+n)² - ¼ - ¼(m-n)² + ¼ = mn. 

Problem A2

Show that any real values satisfying x + y + z = 5, xy + yz + zx = 3 lie between -1 and 13/3.

Solution

We have the solution -1, 3, 3, so -1 is attained. We also have the solution 13/3, 1/3, 1/3, so 13/3 is attained.

We have (x+y)² = (5-z)², xy = 3 - z(x+y) = 3 - z(5-z), so (x-y)² = (x+y)² - 4xy = 25-10z+z² - 4(3-5z+z²) = 13 + 10z -3z² = (13 - 3z)(z + 1). But (x-y)² ≥ 0, so -1 ≤ z ≤ 13/3. 

Problem A3

A graph has 9 points and 36 edges. Each edge is colored red or black, so that every triangle has at least one red side. Show that there are four points with all edges between them red.

Solution

We show first that given any 6 of the points there is a red triangle amongst their edges. Take any point X of the six. If three points are A_i of the six are joined to X by blue edges, then considering the triangles XA_iA_j, each of the edges A_iA_j must be red and we have a red triangle. So we can assume that each point of the six has at least three red edges to other points of the six. Take the points to be A, B, C, D, E, F, with AB, AC, AD all red. Now B has at least two other red edges to the other six. If BC is red, then ABC is red. Similarly if BD is red. So BE and BF are red. Now one of AE, AF, EF must be red, but that gives red triangles ABE, ABF, BEF respectively.

Return to considering all 9 points. Take any point X. If there are 4 points A_i not joined to X by a red edge, then since every triangle XA_iA_j has a red edge, all the edges A_iA_j must be red and we are home. So we can assume that every point has at least 5 red edges.

If every point has exactly 5 red edges, then there are 9·5/2 red edges in total, which is impossible, so some point X must have red edges to 6 other points. But there is a red triangle ABC amongst those points (shown above), so that XABC has all edges red. 

Problem B1

A triangle ABC has all angles smaller than 120^o. An equilateral triangle is constructed on the outside of each side by constructing three new vertices D, E, F. Show that the three lines joining the new vertex of each equilateral triangle to the opposite vertex of ABC meet at a point X. Show that XD + XE + XF = 2(XA + XB + XC).

Solution

A rotation of 60^o about B takes A to F and D to C. So the angle between AD and CF is 60^o. Suppose they meet at X. So ∠BAF = ∠BXF = 60^o, so AFBX is cyclic, so ∠BXF = ∠BAF = 60^o. But a rotation of 60^o about A takes FC to BE, so BX and BE make the same angle with CF, so the must be the same line.

A rotation of 60^o about F takes B to A and X to X'. Evidently FXX' is equilateral. Since ∠AXF = 60^o, A must lie on XX'. But AX' = BX (because of the rotation), so XF = XX' = XA + AX' = XA + XB. Adding the two similar relations gives XD + XE + XF = 2(XA + XB + XC).

 Problem B2

Find all possible positive integers which have at least seven positive divisors and equal one less than the sum of the squares of their sixth and seventh divisors, when the divisors are listed in order of increasing size.

Answer

144, 1984

Solution

Let the number be n and its divisors be 1 = d₁ < d₂ < ... , so we have n + 1 = d₆² + d₇².

Suppose d₆ = ab, d₇ = cd with 1 < a < b, 1 < c < d. Note that d₆ and d₇ must be coprime, because if d divides d₆ and d₇, then it also divides n and hence 1 = n - d₆² - d₇². So a, b, c, d are all distinct. If we must have a < d (or d₆ = ab > a² > d² > cd = d₇), hence ac < ad = d₇. But ac ≠ d₆ and ac divides n (since a and c are coprime and both divide n), so ac < d₆. Hence we have 6 divisors of n all < d₆ (namely 1, a, b, c, d, ac). Contradiction. So at least one of d₆, d₇ is a prime or a prime squared. Neither can be 2 or 4 (because there cannnot be 5 divisors of n less than 4).

But note that d₆ divides n - d₆² = d₇² - 1 = (d₇ - 1)(d₇ + 1). (d₇ ± 1) are coprime except possibly for a factor 2, so if d₆ is an odd prime or odd prime squared, then it divides d₇ - 1 or d₇ + 1. Similarly, if d₇ is an odd prime or odd prime squared, then it divides d₆ - 1 or d₆ + 1.

Suppose first that d₆ is the odd prime or odd prime squared. If d₆ divides d₇ - 1, then d₇ = kd₆ + 1. Hence n = d₆² + k²d₆² + 2kd₆ = d₆(k²d₆ + d₆ + 2k). So d₇ (coprime to d₆) must divide k²d₆ + d₆ + 2k and hence also (k²d₆ + d₆ + 2k) - k(kd₆ + 1) = d₆ + k. So 0 ≤ d₆ + k - kd₆ - 1 = - (k - 1)(d₆ - 1). Hence k = 1.

If d₆ divides d₇ + 1, then d₇ = kd₆ - 1 for some k > 1. Hence n = d₆(k²d₆ + d₆ - 2k), so d₇ divides k²d₆ + d₆ - 2k and hence also d₆ - k. If d₆ - k > 0, then d₆ - k > kd₆ - 1, so (k - 1)(d₆ + 1) < 0. Contradiction. So d₆ - k < 0. But d₇ > |d₆ - k|, so k > 2d₆. But d₆ is a prime or a prime square, so some d_i < d₆ is coprime to d₆. Hence n has another divisor between d₆ and d₆² (namely d_id₆), so k ≤ d₆. Contradiction. So d₆ cannot divide d₇ + 1.

The other case is much easier. If d₇ divides d₆ ± 1, then it must equal d₆ + 1. So we have established that in all cases d₇ = d₆ + 1.

Put d₆ = d. Then d and d+1 are coprime and both divide n, so n = kd(d+1) for some k. But n + 1 = d² + (d+1)², so k = 2 and n = 2d(d+1).

We can still get more out of the fact that d or d+1 is a prime or prime squared. Suppose d is a prime. Then d₁, d₂, d₃, d₄, d₅, d₇, 2d₇ are precisely the factors of 2(d+1). But p^aq^b ... has (a+1)(b+1)... factors, so 2(d+1) = p⁶ for some prime p which must be 2. Hence d+1 = 32, d = 31. That gives n = 1984 and it is easy to check that d₁ = 1, d₂ = 2, d₃ = 4, d₄ = 8, d₅ = 16, d₆ = 31, d₇ = 32, and 1984 = 31² + 32² - 1.

Similarly, if d+1 is a prime, then d₁, d₂, d₃, d₄, d₅, d₆, 2d₆ are precisely the factors of 2d. So 2d = 2⁶ and d = 32, but then d+1 is not prime. Contradiction.

If d is a prime squared, put d = p². If p = 3, then d+1 = 10, and n = 180, but then d₁ = 1, d₂ = 2, d₃ = 3, d₄ = 4, d₅ = 5, d₆ = 6 (not 9). Contradiction. So p > 3. d+1 is even, so we certainly have the factors 1, 2, 4, p, 2p, 4p less than p². Contradiction.

The final case is d+1 a prime squared, so put d+1 = p². If p = 3, then d = 8 and n = 144. Then d₁ = 1, d₂ = 2, d₃ = 3, d₄ = 4, d₅ = 6, d₆ = 8, d₇ = 9 and 144 = 82 + 92 - 1, which is a solution. If p > 3, then d is even, so we have the factors 1, 2, 4, p, 2p, 4p less than p² = d+1, so 4p = d₆ = p² - 1. Contradiction.

Problem B3

Find all real polynomials p(x) such that p(x² + x + 1) = p(x) p(x + 1).

Answer

0, 1, (x² + 1)ⁿ for n = 1, 2, 3, ...

Solution

Suppose p(x) has a real root. Then take k to be the largest real root. But k² + k + 1 > k and is also a real root. Contradiction. So p(x) has no real roots. So p(x) must have even degree. Note also that it is immediate from the relation that the leading coefficient is 1.

It is easy to check that x² + 1 is a solution and the only quadratic solution. Also notice that if q(x) and r(x) are solutions, then so is q(x)r(x), so we might conjecture that the solutions are (x² + 1)ⁿ.

Let p(x) be a solution with degree 2n. Put q(x) = p(x) - (x² + 1)ⁿ. Suppose q(x) ≠ 0. It has no term in x²ⁿ, so let deg q = m < 2n. Hence q(x² + x + 1) - q(x)q(x+1) has degree < 4n. But it equals p(x)((x+1)²+1)ⁿ + p(x+1)(x²+1)ⁿ, which has degree 4n. Contradiction. So we must have q(x) = 0, which shows that the only solution of degree 2n is (x² + 1)ⁿ.

Finally notice that in addition to the solution 1 of degree 0, we also have the solution 0.