8th Australian Mathematical Olympiad Problems 1987

A1.  ABC is an isosceles triangle with AB = AC. M is the midpoint of AC. D is a point on the arc BC of the circumcircle of BMC not containing M, and the ray BD meets the ray AC at E so that DE = MC. Show that MD² = AC·CE and CE² = BC·MD/2.

A2.  Show that (2p)!/(p! p!) - 2 is a multiple of p if p is prime.

A3.  A graph has 20 points and there is an edge between every two points. Each edge is colored red or green. There are two points which are not joined by a path of red edges. Show that every two points are either joined by a green edge or joined to a third point by green edges.

B1.  ABC is a triangle. P and Q are interior points such that ∠PBA = ∠QBC, and ∠PCA = ∠QCB. Show that ∠PAB = ∠QAC.

B2.  m is a fixed even positive integer and n > 1 is a fixed integer. f is a real-valued function defined on the non-negative reals such that f( (x₁^m + x₂^m + ... + x_n^m)/m) = ( |f(x₁)|^m + ... + |f(x_n)|^m)/m for all x_i, f(1988) is non-zero and f(1986) - 1986 is non-zero. Show that f(1987) = 1.

B3.  Show that 1/√1 + 1/√2 + 1/√3 + ... + 1/√n < √(n+1) + √n - √2 for n > 1. 

Solutions

Problem A1

ABC is an isosceles triangle with AB = AC. M is the midpoint of AC. D is a point on the arc BC of the circumcircle of BMC not containing M, and the ray BD meets the ray AC at E so that DE = MC. Show that MD² = AC·CE and CE² = BC·MD/2.

Solution

Cosine rule on MED gives ME² = DE² + MD² - 2MD·DE cos MDE (*). But -cos MDE = cos MDB = cos C = BC/2AC, so (*) becomes (MC + CE)² = DE² + MD² + MD·DE·BC/AC, or 2MC·CE + CE² = MD² + MD·BC/2 (**), since MC = DE and AC = 2MC = 2DE.

Triangles EDM, ECB are similar, so DE/DM = CE/CB. Substituting from this for BC makes (**) become: AC·CE(1 + CE/AC) = MD²(1 + CE/AC), so MD² = AC·CE. Subtracting from (**) gives CE² = MD·BC/2. 

Problem A2

Show that (2p)!/(p! p!) - 2 is a multiple of p if p is prime.

Solution

(2p)!/(p!p!) = (2p/p) ((2p-1)/(p-1)) ... (p+1)/1. Note that 1, ... , p-1 and (2p-1), (2p-2), ... , (p+1) are both complete sets of non-zero residues mod p. So their product is equal mod p. Hence (2p)!/(p!p!) = 2p/p = 2 mod p. 

Problem A3

A graph has 20 points and there is an edge between every two points. Each edge is colored red or green. There are two points which are not joined by a path of red edges. Show that every two points are either joined by a green edge or joined to a third point by green edges.

Solution

Suppose A and B are the points not joined by a path of red edges. Suppose X and Y are any two other points. If the edge XY is green we are done, so assume it is red. If both XA and YA are green we are done, so wlog XA is red. Now YB must be green or we have the red path AXYB. Now XB cannot be red or we have the red path AXB, so XB is green and B is joined to both X and Y by green edges.

It remains to consider the cases where one or other of X, Y belong to {A, B}. Obviously the edge AB must be green, or we would have a red path A to B. That deals with the case where both X and Y belong to {A, B}. So suppose Y = A. If the edge AX is green we are done, so assume it is red. But now XB must be red, or we would have the red path AXB. But now B is joined to A and X by green edges.

Note that 20 is a red herring.

Problem B1

ABC is a triangle. P and Q are interior points such that ∠PBA = ∠QBC, and ∠PCA = ∠QCB. Show that ∠PAB = ∠QAC.

Solution

Using the sine rule repeatedly and putting ∠PBA = x, ∠PCA = y, ∠PAB = z, ∠QAC = z', we have PA/PB = sin x/sin z, PB/PC = sin(C-y)/sin(B-x), PC/PA = sin(A-z)/sin y. So sin z/sin(A-z) = (sin x/sin(B-x))(sin(C-y)/sin y). Similarly, writing down QA/QB etc we get sin z'/sin(A-z') = (sin x/sin(B-x))(sin(C-y)/sin y). Hence sin z sin(A-z') = sin z' sin(A-z). Expanding, sin z(sin A cos z' - cos A sin z') = sin z'(sin A cos z - cos A sin z), so sin z cos z' = sin z' cos z, so tan z = tan z'. But both z and z' lie in the range 0^o to 180^o, so z = z'.

 

Problem B2

m is a fixed even positive integer and n > 1 is a fixed integer. f is a real-valued function defined on the non-negative reals such that f( (x₁^m + x₂^m + ... + x_n^m)/n) = ( |f(x₁)|^m + ... + |f(x_n)|^m)/n for all x_i, f(1988) is non-zero and f(1986) - 1986 is non-zero. Show that f(1987) = 1.

Solution

The absolute values signs are unnecessary since m is even. Putting all x_i = x, for example, we get f(x^m) = f(x)^m. Putting x = 0, 1 gives f(0) = 0 or 1 and f(1) = 0 or 1. Also given any y we can find x such that x^m = y, so f(y) = f(x)^m ≥ 0. In other words f always takes non-negative values.

Substituting back into the main relation gives f( (x₁^m + x₂^m + ... + x_n^m)/n) = (f(x₁)^m + ... + f(x_n)^m)/n = (f(x₁^m) + ... + f(x_n^m) )/n. But given any y_i ≥ 0 we can find x_i ≥ 0 such that y_i = x_i^m, so for any y₁, y₂, ... , y_n we have f( (y₁ + y₂ + ... + y_n)/n) = (f(y₁) + ... + f(y_n))/n.

Taking y₁ = x-1, y₂ = x+1 and any remaining y_i = x (if n > 2) we get f(x) = f(x-1)/n + f(x+1)/n + (n-2)/n f(x), so 2f(x) = f(x-1) + f(x+1). Hence f(0), f(1), f(2), ... form an arithmetic progression. If f(0) = f(1) = 0, then all f(n) = 0, but we are told f(1988) ≠ 0. If f(0) = 0, f(1) = 1, then all f(n) = n, but we are told f(1986) ≠ 1986. If f(0) = 1, f(1) = 0, then f(n) < 0 for n > 1, but we showed above that f(n) is always non-negative. So we must have f(0) = f(1) = 1 and hence f(n) = 1 for all positive integers. 

Problem B3

Show that 1/√1 + 1/√2 + 1/√3 + ... + 1/√n < √(n+1) + √n - √2.

Solution

Induction on n. For n = 1 we have 1 = √2 + 1 - √2. We show that ≤ for n implies < for n+1. It is sufficient to show that 1/√(n+1) < √(n+2) - √n, or √n + 1/√(n+1) < √(n+2). Squaring, that is equivalent to 2√(n/(n+1)) < 2 - 1/(n+1), or squaring again to n/(n+1) < 1 - 1/(n+1) + 1/(4(n+1)²), which is obviously true. 

Solutions are also available in Australian Mathematical Olympiads 1979-1995 by H Lausch and P J Taylor, ISBN 0858896451, published by Australian Mathematics Trust.

[Read More...]

7th Australian Mathematical Olympiad Problems 1986

A1.  Given a positive integer n and real k > 0, what is the largest possible value for (x₁x₂ + x₂x₃ + x₃x₄ + ... + x_n-1x_n), where x_i are non-negative real numbers with sum k?

A2.  What is the smallest tower of 100s that exceeds a tower of 100 threes? In other words, let a₁ = 3, a₂ = 3³, and aⁿ⁺¹ = 3^a_n. Similarly, b₁ = 100, b₂ = 100¹⁰⁰ etc. What is the smallest n for which b_n > a₁₀₀?

A3.  Three chords of the circumcircle bisect the three angles of a triangle. Show that the sum of their lengths exceeds the perimeter of the triangle.

B1.  C is a circle of unit radius. For any line L define d(L) to be the distance between the two points of intersection if L meets C in two points, and zero otherwise. For any point P define f(P) to be the maximum value of d(L) + d(L') for two perpendicular lines through P. Which P have f(P) > 2?

B2.  Define the sequence a₁, a₂, a₃, ... by a₁ = 1, a₂ = b, a_n+2 =2a_n+1 - a_n + 2, where b is a positive integer. Show that for any n we can find an m such that a_na_n+1 = a_m.

B3.  A real polynomial of degree n > 2 has all roots real and positive. The coefficient of xⁿ is 1, the coefficient of x^n-1 is -1. The coefficient of x¹ is non-zero and -n² times the coefficient of x⁰. Show that all the roots are equal. 

Solutions

 
Problem A1

Given a positive integer n and real k > 0, what is the largest possible value for (x₁x₂ + x₂x₃ + x₃x₄ + ... + x_n-1x_n), where x_i are non-negative real numbers with sum k?

Answer

k²/4

Solution

Let x_h = max(x_i). Then x₁x₂ + x₂x₃ + x₃x₄ + ... + x_h-1x_h + x_hx_h+1 + x_h+1x_h+2 + ... + x_n-1x_n ≤ x₁x_h + x₂x_h + ... + x_h-1x_h + x_hx_h+1 + x_hx_h+2 + ... + x_hx_n = x_h(k - x_h) ≤ k²/4 (last step AM/GM). But k²/4 can be realized by x₁ = x₂ = k/2 and others 0. 

Problem A2

What is the smallest tower of 100s that exceeds a tower of 100 threes? In other words, let a₁ = 3, a₂ = 3³, and aⁿ⁺¹ = 3^a_n. Similarly, b₁ = 100, b₂ = 100¹⁰⁰ etc. What is the smallest n for which b_n > a₁₀₀?

Answer

99

Solution

We have 3³ < 100 and hence by a trivial induction a_n+1 < b_n (a_n+1 = 3^a_n < 100^a_n < 100^b_n-1 = b_n).

We claim that a_n+1 > 6b_n-1. Obviously 3³³ > 600 so it is true for n = 2. Suppose it is true for n. Note that 3⁶ = 729 > 600, so a_n+2 > 3^6b_n-1 > 600^b_n-1 = 6^b_n-1b_n > 6b_n.

Problem A3

Three chords of the circumcircle bisect the three angles of a triangle. Show that the sum of their lengths exceeds the perimeter of the triangle.

Solution

Bizarrely, this is a repeat of 82/A3. 

Problem A3

In the triangle ABC, let the angle bisectors of A, B, C meet the circumcircle again at X, Y, Z. Show that AX + BY + CZ is greater than the perimeter of ABC.

Solution

The sine rule gives BC/sin A = CA/sin B = AB/sin C. Put k = BC/sin A, so perimeter = k(sin A + sin B + sin C). Applying sine rule to BCY we have BC/sin Y = BC/sin A = k = BY/sin BCY. But ∠BCY = ∠C + ∠ACY = ∠C + ∠B/2. So BY = k sin(C+B/2). Similarly for the other chords, so AX + BY + CZ = k(sin(C+B/2) + sin(A+C/2) + sin(B+A/2)).

But sin(C+B/2) = sin(90^o + C/2 - A/2) = cos(A/2 - C/2) > cos(A/2 - C/2) sin(A/2 + C/2) = ½ sin A + ½ sin C. Adding the two similar relations gives the required result. Note that we cannot have equality because A + C < 180^o, so sin(A/2 + C/2) < 1.

Problem B1

C is a circle of unit radius. For any line L define d(L) to be the distance between the two points of intersection if L meets C in two points, and zero otherwise. For any point P define f(P) to be the maximum value of d(L) + d(L') for two perpendicular lines through P. Which P have f(P) > 2?

Answer

points inside (but not on) the circle with the same center and radius √(3/2)

Solution

It is obvious that points inside C qualify (take L to be a diameter), and fairly obvious that points on C qualify (L and L' meet C again at the ends of a diameter). So we consider P outside C.

Let O be the center of C. Obviously if PO ≥ √2, then only one of L, L' meets C, so f(P) = 2. So suppose P is close enough for L and L' to meet C.

Let OP = r. Take the angle x as shown. Then d = d(L) + d(L') = 2√(1 - r²cos²x) + 2√(1 - r²sin²x). So d²/4 = 2 - r² + 2√(1 - r² + r⁴sin2xcos2x) = 2 - r² + √(4 - 4r² + r⁴sin2x). That is obviously maximised by taking x = π/4 giving 2 - r² + √(4 - 4r² + r⁴) = 4 - 2r², since r² < 2. So f(P) > 2 iff 4 - 2r² > 1, or r < √(3/2).

Problem B2

Define the sequence a₁, a₂, a₃, ... by a₁ = 1, a₂ = b, a_n+2 =2a_n+1 - a_n + 2, where b is a positive integer. Show that for any n we can find an m such that a_na_n+1 = a_m.

Solution

A trivial induction shows that a_n+2 = (n+1)b + n². So a_n+1a_n+2 = n(n+1)b² + (2n³-n²-n+1)b + n²(n-1)² = a_N+2, where N = nb+n²-n. 

Problem B3

A real polynomial of degree n > 2 has all roots real and positive. The coefficient of xⁿ is 1, the coefficient of x^n-1 is -1. The coefficient of x¹ is non-zero and -n² times the coefficient of x⁰. Show that all the roots are equal.

Solution

Let the roots be a₁, a₂, ... , a_n. Then a₁ + a₂ + ... + a_n = 1 and 1/a₁ + 1/a₂ + ... + 1/a_n = n², so (a₁ + ... + a_n)(1/a₁ + ... + 1/a_n) = n². But (a₁ + ... + a_n)(1/a₁ + ... + 1/a_n) ≥ n² with equality iff all a_i are equal. (A well-known result = prove for example by Cauchy-Schwartz on √a_i and 1/√a_i). 

Solutions are also available in Australian Mathematical Olympiads 1979-1995 by H Lausch and P J Taylor, ISBN 0858896451, published by Australian Mathematics Trust

[Read More...]

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.

[Read More...]

4th Australian Mathematical Olympiad Problems 1983

A1.  Consider the following sequence: 1/1, 2/1, 1/2, 3/1, 2/2, 1/3, 4/1, 3/2, 2/3, 1/4, 5/1, ... , where we list all m/n with m+n = k in order of decreasing m, and then all m/n with m+n = k+1 etc. Each rational appears many times. Find the first five positions of 1/2. What is the position for the nth occurrence of 1/2? Find an expression for the first occurrence of p/q where p < q and p and q are coprime.

A2.  P is a point inside the triangle ABC. Angle PAC = angle PBC. M is the midpoint of AB and L and N are the feet of the perpendiculars from P to BC and CA respectively. Show that ML = MN.

A3.  A box contains w white and b black balls. Two balls taken at random are removed. If they are the same color, then a black ball is put into the box. If they are the opposite color, then a white ball is put into the box. This is repeated until the box contains only one ball. What is the probability that it is white?

B1.  Find all positive integers m, n such that (n+1)^m = n! + 1.

B2.  Find the permutations a₁, a₂, ... , a_n of 1, 2, ... , n which maximise and minimise a₁a₂ + a₂a₃ + ... + a_n-1a_n + a_na₁.

B3.  ABC is right-angled and similar to AB'C'. But ABC and AB'C' have opposite orientation. The right-angles are at B and B'. BC' and B'C meet at X. Show that AX is perpendicular to BB'. 

[Read More...]

3rd Australian Mathematical Olympiad Problems 1982

A1.  If you toss a fair coin n+1 times and I toss it n times, what is the probability that you get more heads?

A2.  Show that the fractional part of (2 + √3)ⁿ tends to 1.

A3.  In the triangle ABC, let the angle bisectors of A, B, C meet the circumcircle again at X, Y, Z. Show that AX + BY + CZ is greater than the perimeter of ABC.

B1.  For what d does a continuous function f: [0, 1] → R with f(0) = f(1) always have a horizontal chord of length d?

B2.  Let p₁ = 2 and p_n+1 be the largest prime divisor of p₁p₂ ... p_n + 1. Show that we never get 5.

B3.  A real number is placed in each cell of an n x n array so that no two rows are identical. Prove that we can delete some column and still have no two rows identical. 

Solutions

Problem A1

If you toss a fair coin n+1 times and I toss it n times, what is the probability that you get more heads?

 

Answer

1/2

 

Solution

Suppose the prob of us getting equal numbers of heads in n tosses each is p. Then by symmetry the prob you get more is (1-p)/2. Now your last toss cannot worsen your position. If you were ahead at n, you will still be ahead whatever the outcome. If we were level at n, then you have 1/2 chance of moving ahead. So your chance of winning is 1/2 - p/2 + p/2 = 1/2.

Comment. Of course, you can also slog out the relevant probabilities.

Problem A2

Show that the fractional part of (2 + √3)ⁿ tends to 1.

 

Solution

(2 + √3)ⁿ + (2 - √3)ⁿ = sum of integral terms on expanding by the binomial theorem. So it has integral part nil. But 0 < 2 - √3 < 1, so (2 - √3)ⁿ tends to zero (but is always positive). Hence result.

Problem A3

In the triangle ABC, let the angle bisectors of A, B, C meet the circumcircle again at X, Y, Z. Show that AX + BY + CZ is greater than the perimeter of ABC.

 

Solution

The sine rule gives BC/sin A = CA/sin B = AB/sin C. Put k = BC/sin A, so perimeter = k(sin A + sin B + sin C). Applying sine rule to BCY we have BC/sin Y = BC/sin A = k = BY/sin BCY. But ∠BCY = ∠C + ∠ACY = ∠C + ∠B/2. So BY = k sin(C+B/2). Similarly for the other chords, so AX + BY + CZ = k(sin(C+B/2) + sin(A+C/2) + sin(B+A/2)).

But sin(C+B/2) = sin(90^o + C/2 - A/2) = cos(A/2 - C/2) > cos(A/2 - C/2) sin(A/2 + C/2) = ½ sin A + ½ sin C. Adding the two similar relations gives the required result. Note that we cannot have equality because A + C < 180^o, so sin(A/2 + C/2) < 1. 

Problem B1

For what d does a continuous function f: [0, 1] → R with f(0) = f(1) always have a horizontal chord of length d?

 

Answer

d ∈ {1, 1/2, 1/3, 1/4, ... }.

 

Solution

We show first that there is always a chord length 1/n. For n = 1, this is obvious, so assume n > 1. Define g(x) = f(x + 1/n) - f(x) for 0 ≤ x ≤ 1 - 1/n. We have to find a zero for g(x). Consider the n values g(0), g(1/n), g(2/n), ... , g((n-1)/n). If any of them are zero we are home. So assume they are all non-zero. Their sum is f(1) - f(0) = 0, so some must be negative and some positive. But g is continuous, so it must assume the intermediate value 0.

Conversely, we construct a function which does not have any chords with lengths in the interval (1/(n+1), 1/n).

We take a piecewise linear function such as that shown. All segments are in one of two directions. The horizontal distance between adjacent parallel lines of one set is DE, the horizontal distance for the other set is AC. The idea is that there are no horizontal lines with lengths between DE and AC. We choose the slope of the dotted lines so that AB = DE. The result is now clear from the diagram. We need A to be (0,0) and X to be (1,0). It is convenient to take the lines to have slopes ±1. Then the first peak has height AB/2. The second peak is BC/2 lower. So we need AB to be a multiple of BC. Suppose we take AB/BC = n. It is clear from the diagram that AX = nAC, so AC = 1/n. Hence AB = 1/(n+1), and BC = 1/(n(n+1)). 

Problem B2

Let p₁ = 2 and p_n+1 be the largest prime divisor of p₁p₂ ... p_n + 1. Show that we never get 5.

 

Solution

p₂ = 3. To get 5 we require that 2·3 p₃p₄...p_n-1 + 1 has largest prime divisor 5. It is obviously not divisible by 2 or 3, so it must be a power of 5. Suppose it is 5^m. Then 5^m-1 is divisible by 5-1 = 4, but 2·3 p₃p₄...p_n-1 is not. Contradiction.

Comment. A popular question. Also British 82/2, Iberoamerican 87/B1, Irish 90/2.

 Problem B3

A real number is placed in each cell of an n x n array so that no two rows are identical. Prove that we can delete some column and still have no two rows identical.

 

Solution

This is the same as Towns 1980 Spring qu 2.

Problem 2

Some numbers are arranged in an n x n array so that no two rows have all their entries identical. Show that one can remove an entire column to leave an n x (n-1) array which has no two rows identical.

 

Solution

We show by induction that we can find a set C of <m columns such that the first m rows restricted to these columns are all different. For m=2, the two rows are known to be different, so they must differ in some column, and we can take C to be that column.

Suppose the result is true for m < n. Then we have a set C of < m columns which distinguish the first m rows. If it also distinguishes the first m+1 rows, then we are done. If not, then row m+1 must match some row i ≤ m on C. Note that it can only match one such row, or the two rows would match each other. But rows i and m+1 cannot be the same, so they must differ in some column. Add this column to C and we get a set C' of < m+1 columns which distinguishes the first m+1 rows. So the result holds for all m ≤ n. But the result for m = n is the required result. 

[Read More...]

2nd Australian Mathematical Olympiad Problems 1981

A1.  Show that in any set of 27 distinct odd positive numbers less than 100 we can always find two with sum 102. How many sets of 26 odd positive numbers less 100 than can we find with no two having sum 102?

A2.  Given a real number 0 < k < 1, define p(x) = (x - k)(x - k²) ... (x - kⁿ)/( (x + k)(x + k²) ... (x + kⁿ) ). Show that if kⁿ⁺¹ ≤ x < 1, then p(x) < p(1).

A3.  ABC is isosceles and M is the midpoint of the base BC. A circle center M touches AB and AC. X lies on the segment AB and Y lies on the segment AC. Show that XY touches the circle iff 4 XB·CY = BC².

B1.  Let N = 915! + 916!/1! + 917!/2! + ... + 1980!/1065! Show that if 1065 < n < 1982, then n divides N.

B2.  A series of parallel lines in three directions divides the plane into equilateral triangles of side 1. Show that if there are vertices a distance h apart and vertices a distance k apart, then there are vertices a distance hk apart. Are there vertices a distance √1981 apart?

B3.  In an archery contest, the two contestants A and B start at x = 0 and walk towards the target at x = 1 together. Each chooses the distance from which he shoots. A has probability x² of hitting the target from x. B has probability x of hitting the target from x. If both hit the target, then the first to shoot wins. What is A's best strategy?

Solutions

 

Problem A1

Show that in any set of 27 distinct odd positive numbers less than 100 we can always find two with sum 102. How many sets of 26 odd positive numbers less 100 than can we find with no two having sum 102?

Answer

2²⁴

Solution

The odd numbers under 100 can be divided into 24 pairs with sum 102 (3+99, 5+97, ... , 49+53) and two other numbers 1, 51. If we take 27, then we must take at least 25 from the pairs and hence both members of at least one pair.

Such a set of 26 odd numbers must include 1 and 51 and one member of each pair. So there are 2²⁴ possibilities. 

Problem A2

Given a real number 0 < k < 1, define p(x) = (x - k)(x - k²) ... (x - kⁿ)/( (x + k)(x + k²) ... (x + kⁿ) ). Show that if kⁿ⁺¹ ≤ x < 1, then p(x) < p(1).

Solution

Note that 0 < kⁿ⁺¹ < kⁿ < k^n-1 < ... < k < 1, so there are various possible cases according to where x lies. If x = kⁱ, then lhs = 0, so the inequality is certainly true. If k < x < 1, then for any 0 < y < x we have (x-y)/(x+y) = 1 - 2y/(x+y) < 1 - 2y/(1+y) = (1-y)/(1+y). We may apply this with y = each kⁱ and multiply to get the result. So we may assume that for some i, we have kⁱ⁺¹ < x < kⁱ. Note that each of (x - k), (x - k²), ... , (x - kⁱ) is negative, whereas each of (x - kⁱ⁺¹), ... , (x - kⁿ⁺¹) is positive, so if i is odd, then lhs is negative and the result certainly holds. So assume i is even.

Now for j > i we have y = k^j < x, so (x-y)/(x+y) < (1-y)/(1+y) - as above. Hence ∏_i<j<n (x-k^j)/(x+k^j) < ∏_i<j<n (1-k^j)/(1+k^j). For the other terms, since there are an even number we may switch the order of x and k^j, so that ∏_1≤j≤i (x-k^j)/(x+k^j) = ∏_1≤j≤i (k^j-x)/(k^j+x). But each term (k^j-x)/(k^j+x) is now positive and > (k^j-kⁱ⁺¹)/(k^j+kⁱ⁺¹) and so ∏_1≤j≤i (x-k^j)/(x+k^j) < ∏_1≤j≤i (k^j-kⁱ⁺¹)/(k^j+kⁱ⁺¹) = ∏_1≤j≤i (1-k^j)/(1+k^j) - we can cancel a power of k from each term and then invert their order.

Finally, we multiply the two inequalities together to get the required result. 

Problem A3

ABC is isosceles and M is the midpoint of the base BC. A circle center M touches AB and AC. X lies on the segment AB and Y lies on the segment AC. Show that XY touches the circle iff 4 XB·CY = BC².

Solution

Suppose XY touches the circle at E. Let AB, AC touch the circle at D, F respectively. Note that by symmetry about AM, ∠BMD = ∠CMF. Also ∠DMX = ∠XME and ∠EMY = ∠YMF. Hence ∠BMD + ∠DMX + ∠YMF = 90^o. Hence ∠CYM = 90^o - ∠YMF = ∠BMX. But ∠B = ∠C, so triangles BXM and CMY are similar. Hence BX/BM = CM/CY, which is the required result.

Now suppose that the equality holds. Take XY' tangent to the circle, then the equality also holds with Y' in place of Y. Hence CY = CY' and so Y must coincide with Y'. Hence XY is tangent.

 Problem B1

Let N = 915! + 916!/1! + 917!/2! + ... + 1980!/1065! Show that if 1065 < n < 1982, then n divides N.

Solution

We have N/915! = 915C915 + 916C915 + ... + 1980C915. But 915C915 = 916C916 and 916C916 + 916C915 = 917C916. Then 917C916 + 917C915 = 918C916 and so on. So N/915! = 1981C916. Hence 916N = 1981!/1065! = 1981·1980 ... 1066.

Note that 2·916 = 1832 appears on the rhs, so for any n ≠ 1832 (and 1065 < n < 1982) we certainly have n a factor of N. But the rhs includes the factors 1603 = 7·229, 1600 = 4·400 and 1832. Hence we can divide through by 916 = 4·229 and conclude that N is also divisible by 1832. 

Problem B2

A series of parallel lines in three directions divides the plane into equilateral triangles of side 1. Show that if there are vertices a distance h apart and vertices a distance k apart, then there are vertices a distance hk apart. Are there vertices a distance √1981 apart?

Answer

Yes.

Solution

We may take the vertices to be the points m + nω in the complex plane, where ω is a complex cube root of 1, so 1 + ω + ω² = 0. Now suppose m + nω and M + Nω are two vertices, then (m + nω)(M + Nω) = mM + mNω + nMω + nNω² = (mN - nN) + (mN + nM - nN)ω, which is also a vertex. So if there are vertices a distance h apart, then by translation, we can take one of them to be the origin and the other to be z. Similarly, if there are vertices a distance k apart, then we can take one to be the origin and the other z'. But then the origin and the vertex zz' are a distance hk apart.

We can take ω = (-1 + i√3)/2, so |m + nω| = √((m - n/2)² + 3n²/4) = √(m² + n² - mn). Thus |3 + ω| = √7, |19 + 6ω| = √283. Their product gives the distance √1981.

Problem B3

In an archery contest, the two contestants A and B start at x = 0 and walk towards the target at x = 1 together. Each chooses the distance from which he shoots. A has probability x² of hitting the target from x. B has probability x of hitting the target from x. If both hit the target, then the first to shoot wins. What is A's best strategy?

Solution

If the first player to shoot hits the target then he wins. If he misses, then the other player waits until he is up against the target and cannot miss, so if the first player to shoot misses, then he loses. So if A shoots first at x, then he has a prob x² of winning, whereas if B shoots first at x, then A has a prob 1-x of winning. Put k = (√5-1)/2 = 0.618... . Then for x < k, we have x² < 1-x, so it is better for A if B shoots first. Thus whilst x < k, A does nothing and hopes that B shoots. Conversely, if x > k, then x² > 1-x, so it is worse for A if B shoots first. Moreover, the longer he waits the worse his position if B manages to shoot first.

Thus A's strategy is as follows. If B shoots at x < k, then he waits until he reaches the target before shooting. If B has not shot at x = k, then A shoots.

[Read More...]

1st Australian Mathematical Olympiad Problems 1979

1.  A graph with 10 points and 35 edges is constructed as follows. Every vertex of one pentagon is joined to every edge of another pentagon. Each edge is colored black or white, so that there are no monochrome triangles. Show that all 10 edges of the two pentagons have the same color.

2.  Two circles (not necessarily equal) intersect at A and B. A point P travels clockwise around the first circle at a constant speed, completing one revolution a minute. Another point Q travels clockwise around the second circle at a constant speed, also completing one revolution a minute. The two points pass through A simultaneously. Show that P, B and Q are collinear and that there is a fixed point C such that CP = CQ at all times.

3.  8 flower pots A, B, C, D, E, F, G, H are arranged in a circle. A frog starts at A and jumps to an adjacent pot (B or H). The frog always jumps to an adjacent pot, makes n jumps, ends up at E, but does not visit E until then. Show that n must be even and that the number of possible routes is ( (2 + √2)^m - (2 - √2)^m)/√2, where n = 2m+2. 

Solutions

Problem 1

A graph with 10 points and 35 edges is constructed as follows. Every vertex of one pentagon is joined to every edge of another pentagon. Each edge is colored black or white, so that there are no monochrome triangles. Show that all 10 edges of the two pentagons have the same color.

 

Solution

This surprisingly awkward. Label one pentagon A₁A₂A₃A₄A₅ and the other B₁B₂B₃B₄B₅. Suppose one of the pentagon edges AA' from A is black. Suppose 3 edges from A to the other pentagon are black. Then two of the points in the other pentagon (joined to A by a black edge) must be joined by an edge, which must be white. Call them B and B'. But the triangle AA'B has two black edges AA' and AB, so the third A'B must be white. Similarly, AA'B' has AA' and AB' black, so A'B' must be white. But now A'BB' has all edges white. Contradiction. So at most 2 edges from A to the other pentagon are black.

If the other pentagon edge from A is white, then the same argument would show that at most 2 edges from A to the other pentagon are white. But there are 5 such edges. So the other pentagon edge from A must be black. Repeating the argument allows us to go around the pentagon and deduce that all its edges are black.

Similarly, we can show that the other pentagon is monochrome. Suppose one is white and one is black. Take A to be a vertex of the black pentagon. Then the argument above shows that 3 of the edges from A to the other pentagon must be white. But two of the points in the other pentagon joined to A by a white edge must be joined and that gives a white triangle. Contradiction. So the two pentagons are the same color. 

Problem 2

Two circles (not necessarily equal) intersect at A and B. A point P travels clockwise around the first circle at a constant speed, completing one revolution a minute. Another point Q travels clockwise around the second circle at a constant speed, also completing one revolution a minute. The two points pass through A simultaneously. Show that P, B and Q are collinear and that there is a fixed point C such that CP = CQ at all times.

 

Solution

Let the circles have centers O, O'. Let C be the reflection of A in the perpendicular bisector of OO'. We show that triangles COP, QO'C are congruent. We have OP = OA (pts on circle) = O'C (reflection). Also OC = O'A (reflection) = O'Q (pts on circle). Also ∠AOP = ∠AO'Q (P and Q circle at same rate), and ∠AOC= ∠AO'C (reflection), so ∠COP = ∠CO'Q. So the triangles are congruent. Hence CP = CQ.

Now ∠ABP = ½∠AOP or 180^o-½∠AOP, and ∠ABQ = ½∠AO'Q or 180^o-½∠AO'Q. Hence ∠ABP = ∠ABQ or ∠ABP + ∠ABQ = 180^o. Either way, P,Q,B are collinear.

This is almost the same as IMO 79/A3.

Problem 3

8 flower pots A, B, C, D, E, F, G, H are arranged in a circle. A frog starts at A and jumps to an adjacent pot (B or H). The frog always jumps to an adjacent pot, makes n jumps, ends up at E, but does not visit E until then. Show that n must be even and that the number of possible routes is ( (2 + √2)^m - (2 - √2)^m)/√2, where n = 2m+2.

 

Solution

Let m be the number of clockwise jumps. Then n-m is the number of anticlockwise jumps and we have m - (n-m) = ±4, so n = 2m±4, which is even. So the number of ways is zero for n odd.

Let u_n be the number of routes from A, and let v_n be the number of routes from C. By symmetry the number of routes from G is also v_n. Now consider u_n+2 (for n > 0). After 2 jumps, the frog is at A (2 possibilities), C (1 possibility) or G (1 possibility), so u_n+2 = 2u_n + 2v_n (1). Similarly, v_n+2 = 2v_n + u_n (2) for n > 0 (note that the second jump cannot take the frog to E because the frog may not reach E until its last jump). Writing (1) as 2v_n = u_n+2 - 2u_n and substituting in (2) we get u_n+4 - 4u_n+2 + 2u_n = 0.

Put u_2m+2 = a_m, then we have a_m+2 - 4a_m+1 + 2a_m = 0. That has solution a_m = A(2+√2)^m + B(2-√2)^m for some constants A, B. But it is obvious that a₀ = u₂ = 0, a₁ = u₄ = 2, so A + B = 0, 2(A+B) + √2 (A-B) = 2. Hence A = 1/√2, B = -1/√2.

[Read More...]