37th International Mathematical Olympiad 1996 Problems & Solutions

A1. We are given a positive integer r and a rectangular board divided into 20 x 12 unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is √r. The task is to find a sequence of moves leading between two adjacent corners of the board which lie on the long side. (a) Show that the task cannot be done if r is divisible by 2 or 3.

(b) Prove that the task is possible for r = 73.

A2. Let P be a point inside the triangle ABC such that ∠APB - ∠ACB = ∠APC - ∠ABC. Let D, E be the incenters of triangles APB, APC respectively. Show that AP, BD, CE meet at a point.

A3. Let S be the set of non-negative integers. Find all functions f: S→S such that f(m + f(n)) = f(f(m)) + f(n) for all m, n.

B1. The positive integers a, b are such that 15a + 16b and 16a - 15b are both squares of positive integers. What is the least possible value that can be taken on by the smaller of these two squares?

B2. Let ABCDEF be a convex hexagon such that AB is parallel to DE, BC is parallel to EF, and CD is parallel to FA. Let R_A, R_C, R_E denote the circumradii of triangles FAB, BCD, DEF respectively, and let p denote the perimeter of the hexagon. Prove that: R_A + R_C + R_E ≥ p/2.

B3. Let p, q, n be three positive integers with p + q < n. Let x₀, x₁, ... , x_n be integers such that x₀ = x_n = 0, and for each 1 ≤ i ≤ n, x_i - x_i-1 = p or -q. Show that there exist indices i < j with (i, j) not (0, n) such that x_i = x_j.

Solutions

Problem A1

We are given a positive integer r and a rectangular board divided into 20 x 12 unit squares. The following moves are permitted on the board: one can move from one square to another only if the distance between the centers of the two squares is √r. The task is to find a sequence of moves leading between two adjacent corners of the board which lie on the long side.

(a) Show that the task cannot be done if r is divisible by 2 or 3.
(b) Prove that the task is possible for r = 73.
(c) Can the task be done for r = 97?

Answer

No.

Solution

(a) Suppose the move is a units in one direction and b in the orthogonal direction. So a² + b² = r. If r is divisible by 2, then a and b are both even or both odd. But that means that we can only access the black squares or the white squares (assuming the rectangle is colored like a chessboard). The two corners are of opposite color, so the task cannot be done. All squares are congruent to 0 or 1 mod 3, so if r is divisible by 3, then a and b must both be multiples of 3. That means that if the starting square has coordinates (0,0), we can only move to squares of the form (3m,3n). The required destination is (19,0) which is not of this form, so the task cannot be done.

(b) If r = 73, then we must have a = 8, b = 3 (or vice versa). There are 4 types of move:

A: (x,y) to (x+8,y+3)
B: (x,y) to (x+3,y+8)
C: (x,y) to (x+8,y-3)
D: (x,y) to (x+3,y-8)

We regard (x,y) to (x-8,y-3) as a negative move of type A, and so on. Then if we have a moves of type A, b of type B and so on, then we require:

8(a + c) + 3(b + d) = 19; 3(a - c) + 8(b - d) = 0.

A simple solution is a = 5, b = -1, c = -3, d = 2, so we start by looking for solutions of this type. After some fiddling we find:

(0,0) to (8,3) to (16,6) to (8,9) to (11,1) to (19,4) to (11,7) to (19,10) to (16,2) to (8,5) to (16,8) to (19,0).

(c) If r = 97, then we must have a = 9, b = 4. As before, assume we start at (0,0). A good deal of fiddling around fails to find a solution, so we look for reasons why one is impossible. Call moves which change y by 4 "toggle" moves. Consider the central strip y = 4, 5, 6 or 7. Toggle moves must toggle us in and out of the strip. Non-toggle moves cannot be made if we are in the strip and keep us out of it if we are out of it. Toggle moves also change the parity of the x-coordinate, whereas non-toggle moves do not. Now we start and finish out of the strip, so we need an even number of toggle moves. On the other hand, we start with even x and end with odd x, so we need an odd number of toggle moves. Hence the task is impossible.

Problem A2

Let P be a point inside the triangle ABC such that ∠APB - ∠ACB = ∠APC - ∠ABC. Let D, E be the incenters of triangles APB, APC respectively. Show that AP, BD, CE meet at a point.

Solution

We need two general results: the angle bisector theorem; and the result about the feet of the perpendiculars from a general point inside a triangle. The second is not so well-known. Let P be a general point in the triangle ABC with X, Y, Z the feet of the perpendiculars to BC, CA, AB. Then PA = YZ/sin A and ∠APB - ∠C = ∠XZY. To prove the first part: AP = AY/sin APY = AY/sin AZY (since AYPZ is cyclic) = YZ/sin A (sine rule). To prove the second part: ∠XZY = ∠XZP + ∠YZP = ∠XBP + ∠YAP = 90^o - ∠XPB + 90^o - ∠YPA = 180^o - (360^o - ∠APB - ∠XPY) = -180^o + ∠APB + (180^o - ∠C) = ∠APB - ∠C.

So, returning to the problem, ∠APB - ∠C = ∠XZY and ∠APC - ∠B = ∠XYZ. Hence XYZ is isosceles: XY = XZ. Hence PC sin C = PB sin B. But AC sin C = AB sin B, so AB/PB = AC/PC. Let the angle bisector BD meet AP at W. Then, by the angle bisector theorem, AB/PB = AW/WP. Hence AW/WP = AC/PC, so, by the angle bisector theorem, CW is the bisector of angle ACP, as required.

Problem A3

Let S be the set of non-negative integers. Find all functions f: S→S such that f(m + f(n)) = f(f(m)) + f(n) for all m, n.

Solution

Setting m = n = 0, the given relation becomes: f(f(0)) = f(f(0)) + f(0). Hence f(0) = 0. Hence also f(f(0)) = 0. Setting m = 0, now gives f(f(n)) = f(n), so we may write the original relation as f(m + f(n)) = f(m) + f(n).

So f(n) is a fixed point. Let k be the smallest non-zero fixed point. If k does not exist, then f(n) is zero for all n, which is a possible solution. If k does exist, then an easy induction shows that f(qk) = qk for all non-negative integers q. Now if n is another fixed point, write n = kq + r, with 0 ≤ r < k. Then f(n) = f(r + f(kq)) = f(r) + f(kq) = kq + f(r). Hence f(r) = r, so r must be zero. Hence the fixed points are precisely the multiples of k.

But f(n) is a fixed point for any n, so f(n) is a multiple of k for any n. Let us take n₁, n₂, ... , n_k-1 to be arbitrary non-negative integers and set n₀ = 0. Then the most general function satisfying the conditions we have established so far is:

f(qk + r) = qk + n_rk for 0 ≤ r < k.

We can check that this satisfies the functional equation. Let m = ak + r, n = bk + s, with 0 ≤ r, s < k. Then f(f(m)) = f(m) = ak + n_rk, and f(n) = bk + n_sk, so f(m + f(n)) = ak + bk + n_rk + n_sk, and f(f(m)) + f(n) = ak + bk + n_rk + n_sk. So this is a solution and hence the most general solution.

Problem B1

The positive integers a, b are such that 15a + 16b and 16a - 15b are both squares of positive integers. What is the least possible value that can be taken on by the smaller of these two squares?

Answer

481².

Solution

Put 15a ± 16b = m², 16a - 15b = n². Then 15m² + 16n² = 481a = 13·37a. The quadratic residues mod 13 are 0, ±1, ±3, ±4, so the residues of 15m² are 0, ±2, ±5, ±6, and the residues of 16n² are 0, ±1, ±3, ±4. Hence m and n must both be divisible by 13. Similarly, the quadratic residues of 37 are 0, ±1, ±3, ±4, ±7, ±9, ±10, ±11, ±12, ±16, so the residues of 15m² are 0, ±2, ±5, ±6, ±8, ±13, ±14, ±15, ±17, ±18, and the residues of 16n² are 0, ±1, ±3, ±4, ±7, ±9, ±10, ±11, ±12, ±16. Hence m and n must both be divisible by 37. Put m = 481m', n = 481n' and we get: a = 481(15m'² + 16n'²). We also have 481b = 16m² - 15n² and hence b = 481(16m'² - 15n'²). The smallest possible solution would come from putting m' = n' = 1 and indeed that gives a solution.

This solution is straightforward, but something of a slog - all the residues have to be calculated. A more elegant variant is to notice that m⁴ + n⁴ = 481(a² + b²). Now if m and n are not divisible by 13 we have m⁴ + n⁴ = 0 (mod 13). Take k so that km = 1 (mod 13), then (nk)⁴ = -(mk)⁴ = -1 (mod 13). But that is impossible because then (nk)¹² = -1 (mod 13), but x¹² = 1 (mod 13) for all non-zero residues. Hence m and n are both divisible by 13. The same argument shows that m and n are both divisible by 37.

Problem B2

Let ABCDEF be a convex hexagon such that AB is parallel to DE, BC is parallel to EF, and CD is parallel to FA. Let R_A, R_C, R_E denote the circumradii of triangles FAB, BCD, DEF respectively, and let p denote the perimeter of the hexagon. Prove that:

R_A + R_C + R_E ≥ p/2.

Solution

The starting point is the formula for the circumradius R of a triangle ABC: 2R = a/sin A = b/sin B = c/sin C. [Proof: the side a subtends an angle 2A at the center, so a = 2R sin A.] This gives that 2R_A = BF/sin A, 2R_C = BD/sin C, 2R_E = FD/sin E. It is clearly not true in general that BF/sin A > BA + AF, although it is true if angle FAB ≥ 120^o, so we need some argument that involves the hexagon as a whole.

Extend sides BC and FE and take lines perpendicular to them through A and D, thus forming a rectangle. Then BF is greater than or equal to the side through A and the side through D. We may find the length of the side through A by taking the projections of BA and AF giving AB sin B + AF sin F. Similarly the side through D is CD sin C + DE sin E. Hence:

2BF ≥ AB sin B + AF sin F + CD sin C + DE sin E. Similarly:

2BD ≥ BC sin B + CD sin D + AF sin A + EF sin E, and

2FD ≥ AB sin A + BC sin C + DE sin D + EF sin F.

Hence 2BF/sin A + 2BD/sin C + 2FD/sin E ≥ AB(sin A/sin E + sin B/sin A) + BC(sin B/sin C + sin C/sin E) + CD(sin C/sin A + sin D/sin C) + DE(sin E/sin A + sin D/sin E) + EF(sin E/sin C + sin F/sin E) + AF(sin F/sin A + sin A/sin C).

We now use the fact that opposite sides are parallel, which implies that opposite angles are equal: A = D, B = E, C = F. Each of the factors multiplying the sides in the last expression now has the form x + 1/x which has minimum value 2 when x = 1. Hence 2(BF/sin A + BD/sin C + FD/sin E) ≥ 2p and the result is proved.

Problem B3

Let p, q, n be three positive integers with p + q < n. Let x₀, x₁, ... , x_n be integers such that x₀ = x_n = 0, and for each 1 ≤ i ≤ n, x_i - x_i-1 = p or -q. Show that there exist indices i < j with (i, j) not (0, n) such that x_i = x_j.

Solution

Let x_i - x_i-1 = p occur r times and x_i - x_i-1 = -q occur s times. Then r + s = n and pr = qs. If p and q have a common factor d, the y_i = x_i/d form a similar set with p/d and q/d. If the result is true for the y_i then it must also be true for the x_i. So we can assume that p and q are relatively prime. Hence p divides s. Let s = kp. If k = 1, then p = s and q = r, so p + q = r + s = n. But we are given p + q < n. Hence k > 1. Let p + q = n/k = h.

Up to this point everything is fairly obvious and the result looks as though it should be easy, but I did not find it so. Some fiddling around with examples suggested that we seem to get x_i = x_j for j = i + h. We observe first that x_i+h - x_i must be a multiple of h. For suppose e differences are p, and hence h-e are -q. Then x_i+h - x_i = ep - (h - e)q = (e - q)h.

The next step is not obvious. Let d_i = x_i+h - x_i. We know that all d_is are multiples of h. We wish to show that at least one is zero. Now d_i+1 - d_i = (x_i+h+1 - x_i+h) - (x_i+1 - x_i) = (p or -q) - (p or -q) = 0, h or -h. So if neither of d_i nor d_i+1 are zero, then either both are positive or both are negative (a jump from positive to negative would require a difference of at least 2h). Hence if none of the d_is are zero, then all of them are positive, or all of them are negative. But d₀ + d_h + ... + d_kh is a concertina sum with value x_n - x₀ = 0. So this subset of the d_is cannot all be positive or all negative. Hence at least one d_i is zero.