38th International Mathematical Olympiad 1997 Problems & Solutions

A1. In the plane the points with integer coordinates are the vertices of unit squares. The squares are colored alternately black and white as on a chessboard. For any pair of positive integers m and n, consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths m and n, lie along the edges of the squares. Let S₁ be the total area of the black part of the triangle, and S₂ be the total area of the white part. Let f(m, n) = |S₁ - S₂|. (a) Calculate f(m, n) for all positive integers m and n which are either both even or both odd.

(b) Prove that f(m, n) ≤ max(m, n)/2 for all m, n.

A2. The angle at A is the smallest angle in the triangle ABC. The points B and C divide the circumcircle of the triangle into two arcs. Let U be an interior point of the arc between B and C which does not contain A. The perpendicular bisectors of AB and AC meet the line AU at V and W, respectively. The lines BV and CW meet at T. Show that AU = TB + TC.

A3. Let x₁, x₂, ... , x_n be real numbers satisfying |x₁ + x₂ + ... + x_n| = 1 and |x_i| ≤ (n+1)/2 for all i. Show that there exists a permutation y_i of x_i such that |y₁ + 2y₂ + ... + ny_n| ≤ (n+1)/2.

B1. An n x n matrix whose entries come from the set S = {1, 2, ... , 2n-1} is called a silver matrix if, for each i = 1, 2, ... , n, the ith row and the ith column together contain all elements of S. Show that: (a) there is no silver matrix for n = 1997;

(b) silver matrices exist for infinitely many values of n.

B2. Find all pairs (a, b) of positive integers that satisfy a^b² = b^a.

B3. For each positive integer n, let f(n) denote the number of ways of representing n as a sum of powers of 2 with non-negative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For example, f(4) = 4, because 4 can be represented as 4, 2 + 2, 2 + 1 + 1 or 1 + 1 + 1 + 1. Prove that for any integer n ≥ 3, 2^n²/4 < f(2ⁿ) < 2^n²/2.

Solutions

Problem A1

In the plane the points with integer coordinates are the vertices of unit squares. The squares are colored alternately black and white as on a chessboard. For any pair of positive integers m and n, consider a right-angled triangle whose vertices have integer coordinates and whose legs, of lengths m and n, lie along the edges of the squares. Let S₁ be the total area of the black part of the triangle, and S₂ be the total area of the white part. Let f(m, n) = |S₁ - S₂|.

(a) Calculate f(m, n) for all positive integers m and n which are either both even or both odd.
(b) Prove that f(m, n) ≤ max(m, n)/2 for all m, n.
(c) Show that there is no constant C such that f(m, n) < C for all m, n.

Solution

(a) If m and n are both even, then f(m,n) = 0. Let M be the midpoint of the hypoteneuse. The critical point is that M is a lattice point. If we rotate the triangle through 180 to give the other half of the rectangle, we find that its coloring is the same. Hence S₁ and S₂ for the triangle are each half their values for the rectangle. But the values for the rectangle are equal, so they must also be equal for the triangle and hence f(m,n) = 0.

If m and n are both odd, then the midpoint of the hypoteneuse is the center of a square and we may still find that the coloring of the two halves of the rectangle is the same. This time S₁ and S₂ differ by one for the rectangle, so f(m,n) = 1/2.

(b) The result is immediate from (a) for m and n of the same parity. The argument in (a) fails for m and n with opposite parity, because the two halves of the rectangle are oppositely colored. Let m be the odd side. Then if we extend the side length m by 1 we form a new triangle which contains the original triangle. But it has both sides even and hence S₁ = S₂. The area added is a triangle base 1 and height n, so area n/2. The worst case would be that all this area was the same color, in which case we would get f(m,n) = n/2. But n <= max(m,n), so this establishes the result.

(c) Intuitively, it is clear that if the hypoteneuse runs along the diagonal of a series of black squares, and we then extend one side, the extra area taken in will be mainly black. We need to make this rigorous. For the diagonal to run along the diagonal of black squares we must have n = m. It is easier to work out the white area added by extending a side. The white area takes the form of a series of triangles each similar to the new n+1 x n triangle. The biggest has sides 1 and n/(n+1). The next biggest has sides (n-1)/n and (n-1)/(n+1), the next biggest (n-2)/n and (n-2)/(n+1) and so on, down to the smallest which is 1/n by 1/(n+1). Hence the additional white area is 1/2 (n/(n+1) + (n-1)²/(n(n+1)) + (n-2)²/(n(n+1)) + ... + 1/(n(n+1)) ) = 1/(2n(n+1)) (n² + ... + 1²) = (2n+1)/12. Hence the additional black area is n/2 - (2n+1)/12 = n/3 - 1/12 and the black excess in the additional area is n/6 - 1/6. If n is even, then f(n,n) = 0 for the original area, so for the new triangle f(n+1,n) = (n-1)/6 which is unbounded.

Problem A2

The angle at A is the smallest angle in the triangle ABC. The points B and C divide the circumcircle of the triangle into two arcs. Let U be an interior point of the arc between B and C which does not contain A. The perpendicular bisectors of AB and AC meet the line AU at V and W, respectively. The lines BV and CW meet at T. Show that AU = TB + TC.

Solution

Extend BV to meet the circle again at X, and extend CW to meet the circle again at Y. Then by symmetry (since the perpendicular bisectors pass through the center of the circle) AU = BX and AU = CY. Also arc AX = arc BU, and arc AY = arc UC. Hence arc XY = arc BC and so angle BYC = angle XBY and hence TY = TB. So AU = CY = CT + TY = CT + TB.

Problem A3

Let x₁, x₂, ... , x_n be real numbers satisfying |x₁ + x₂ + ... + x_n| = 1 and |x_i| ≤ (n+1)/2 for all i. Show that there exists a permutation y_i of x_i such that |y₁ + 2y₂ + ... + ny_n| ≤ (n+1)/2.

Solution

Without loss of generality we may assume x₁ + ... + x_n = +1. [If not just reverse the sign of every x_i.] For any given arrangement x_i we use sum to mean x₁ + 2x₂ + 3x₃ + ... + nx_n. Now if we add together the sums for x₁, x₂, ... , x_n and the reverse x_n, x_n-1, ... , x₁, we get (n+1)(x₁ + ... + x_n) = n+1. So either we are home with the original arrangement or its reverse, or they have sums of opposite sign, one greater than (n+1)/2 and one less than -(n+1)/2.

A transposition changes the sum from ka + (k+1)b + other terms to kb + (k+1)a + other terms. Hence it changes the sum by |a - b| (where a, b are two of the x_i) which does not exceed n+1. Now we can get from the original arrangement to its reverse by a sequence of transpositions. Hence at some point in this sequence the sum must fall in the interval [-(n+1)/2, (n+1)/2] (because to get from a point below it to a point above it in a single step requires a jump of more than n+1). That point gives us the required permutation.

Problem B1

An n x n matrix whose entries come from the set S = {1, 2, ... , 2n-1} is called silver matrix if, for each i = 1, 2, ... , n, the ith row and the ith column together contain all elements of S. Show that:

(a) there is no silver matrix for n = 1997;
(b) silver matrices exist for infinitely many values of n.

Solution

(a) If we list all the elements in the rows followed by all the elements in the columns, then we have listed every element in the array twice, so each number in S must appear an even number of times. But considering the ith row with the ith column, we have also given n complete copies of S together with an additional copy of the numbers on the diagonal. If n is odd, then each of the 2n-1 numbers appears an odd number of times in the n complete copies, and at most n numbers can have this converted to an even number by an appearance on the diagonal. So there are no silver matrices for n odd. In particular, there is no silver matrix for n = 1997.

(b) Let A_i,j be an n x n silver matrix with 1s down the main diagonal. Define the 2n x 2n matrix B_i,j with 1s down the main diagonal as follows: B_i,j = A_i,j; B_i+n,j+n = A_i,j; B_i,j+n = 2n + A_i,j; B_i+n,j = 2n + A_i,j for i not equal j and B_i+n,i = 2n. We show that B_i,j is silver. Suppose i ≤ n. Then the first half of the ith row is the ith row of A_i,j, and the top half of the ith column is the ith column of A_i,j, so between them those two parts comprise the numbers from 1 to 2n - 1. The second half of the ith row is the ith row of A_i,j with each element increased by 2n, and the bottom half of the ith column is the ith column of A_i,j with each element increased by 2n, so between them they give the numbers from 2n + 1 to 4n - 1. The only exception is that A_i+n,i = 2n instead of 2n + A_i,i. We still get 2n + A_i,i because it was in the second half of the ith row (these two parts do not have an element in common). The 2n fills the gap so that in all we get all the numbers from 1 to 4n - 1.

An exactly similar argument works for i > n. This time the second half of the row and the second half of the column (which overlap by one element) give us the numbers from 1 to 2n - 1, and the first halves (which do not overlap) give us 2n to 4n - 1. So B_i,j is silver. Hence there are an infinite number of silver matrices.

Problem B2

Find all pairs (a, b) of positive integers that satisfy a^b² = b^a.

Answer

(1,1), (16,2), (27,3).

Solution

Notice first that if we have a^m = bⁿ, then we must have a = c^e, b = c^f, for some c, where m=fd, n=ed and d is the greatest common divisor of m and n. [Proof: express a and b as products of primes in the usual way.]

In this case let d be the greatest common divisor of a and b², and put a = de, b² = df. Then for some c, a = c^e, b = c^f. Hence f c^e = e c^2f. We cannot have e = 2f, for then the c's cancel to give e = f. Contradiction. Suppose 2f > e, then f = e c^2f-e. Hence e = 1 and f = c^2f-1. If c = 1, then f = 1 and we have the solution a = b = 1. If c ≥ 2, then c^2f-1 ≥ 2^f > f, so there are no solutions.

Finally, suppose 2f < e. Then e = f c^e-2f. Hence f = 1 and e = c^e-2. c^e-2 ≥ 2^e-2 ≥ e for e ≥ 5, so we must have e = 3 or 4 (e > 2f = 2). e = 3 gives the solution a = 27, b = 3. e = 4 gives the solution a = 16, b = 2.

Problem 6

For each positive integer n, let f(n) denote the number of ways of representing n as a sum of powers of 2 with non-negative integer exponents. Representations which differ only in the ordering of their summands are considered to be the same. For example, f(4) = 4, because 4 can be represented as 4, 2 + 2, 2 + 1 + 1 or 1 + 1 + 1 + 1. Prove that for any integer n ≥ 3, 2^n²/4 < f(2ⁿ) < 2^n²/2.

Solution

The key is to derive a recurrence relation for f(n) [not for f(2ⁿ)]. If n is odd, then the sum must have a 1. In fact, there is a one-to-one correspondence between sums for n and sums for n-1. So:

f(2n+1) = f(2n)

Now consider n even. The same argument shows that there is a one-to-one correspondence between sums for n-1 and sums for n which have a 1. Sums which do not have a 1 are in one-to-one correspondence with sums for n/2 (just halve each term). So:

f(2n) = f(2n - 1) + f(n) = f(2n - 2) + f(n).

The upper limit is now almost immediate. First, the recurrence relations show that f is monotonic increasing. Now apply the second relation repeatedly to f(2ⁿ⁺¹⁾ to get:

f(2ⁿ⁺¹) = f(2ⁿ⁺¹ - 2ⁿ) + f(2ⁿ - 2^n-1 + 1) + ... + f(2ⁿ - 1) + f(2ⁿ) = f(2ⁿ) + f(2ⁿ - 1 ) + ... + f(2^n-1 + 1) + f(2ⁿ) (*)

and hence f(2ⁿ⁺¹) ≥ (2^n-1 + 1)f(2ⁿ)

We can now establish the upper limit by induction. It is false for n = 1 and 2, but almost true for n = 2, in that: f(2²) = 2^2²/2. Now if f(2ⁿ) ≤ 2^n²/2, then the inequality just established shows that f(2ⁿ⁺¹) < 2ⁿ2^n²/2 < 2^(n²+2n+1)/2 = 2^(n+1)²/2, so it is true for n + 1. Hence it is true for all n > 2.

Applying the same idea to the lower limit does not work. We need something stronger. We may continue (*) inductively to obtain f(2ⁿ⁺¹) = f(2ⁿ) + f(2ⁿ - 1) + ... + f(3) + f(2) + f(1) + 1. (**) We now use the following lemma:

f(1) + f(2) + ... + f(2r) ≥ 2r f(r)

We group the terms on the lhs into pairs and claim that f(1) + f(2r) ≥ f(2) + f(2r-1) ≥ f(3) + f(2r-2) ≥ ... ≥ f(r) + f(r+1). If k is even, then f(k) = f(k+1) and f(2r-k) = f(2r+1-k), so f(k) + f(2r+1-k) = f(k+1) + f(2r-k). If k is odd, then f(k+1) = f(k) + f((k+1)/2) and f(2r+1-k) = f(2r-k) + f((2r-k+1)/2), but f is monotone so f((k+1)/2) ≤ f((2r+1-k)/2) and hence f(k) + f(2r+1-k) ≥ f(k+1) + f(2r-k), as required.

Applying the lemma to (**) gives f(2ⁿ⁺¹⁾ > 2ⁿ⁺¹f(2^n-1). This is sufficient to prove the lower limit by induction. It is true for n = 1. Suppose it is true for n. Then f(2ⁿ⁺¹) > 2ⁿ⁺¹2^(n-1)²/4 = 2^{(n²-2n+1+4n+4)/4} > 2^(n+1)²/4, so it is true for n+1.