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.