17th International Mathematical Olympiad 1975 Problems & Solutions

A1.  Let x₁ ≥ x₂ ≥ ... ≥ x_n, and y₁ ≥ y₂ ≥ ... ≥ y_n be real numbers. Prove that if z_i is any permutation of the y_i, then:       ∑_1≤i≤n (x_i - y_i)² ≤ ∑_1≤i≤n (x_i - z_i)².

A2.  Let a₁ < a₂ < a₃ < ... be positive integers. Prove that for every i ≥ 1, there are infinitely many a_n that can be written in the form a_n = ra_i + sa_j, with r, s positive integers and j > i.

A3.  Given any triangle ABC, construct external triangles ABR, BCP, CAQ on the sides, so that ∠PBC = 45^o, ∠PCB = 30^o, ∠QAC = 45^o, ∠QCA = 30^o, ∠RAB = 15^o, ∠RBA = 15^o. Prove that ∠QRP = 90^o and QR = RP.

B1.  Let A be the sum of the decimal digits of 4444⁴⁴⁴⁴, and B be the sum of the decimal digits of A. Find the sum of the decimal digits of B.

B2.  Find 1975 points on the circumference of a unit circle such that the distance between each pair is rational, or prove it impossible.

B3.  Find all polynomials P(x, y) in two variables such that: (1)  P(tx, ty) = tⁿP(x, y) for some positive integer n and all real t, x, y;

(2)  for all real x, y, z: P(y + z, x) + P(z + x, y) + P(x + y, z) = 0;

(3)  P(1, 0) = 1. 

Problem A1

Let x₁ ≥ x₂ ≥ ... ≥ x_n, and y₁ ≥ y₂ ≥ ... ≥ y_n be real numbers. Prove that if z_i is any permutation of the y_i, then:

      ∑₁ⁿ (x_i - y_i)² ≤ ∑₁ⁿ (x_i - z_i)².

 

Solution

If x ≥ x' and y ≥ y', then (x - y)² + (x' - y')² ≤ (x - y')² + (x' - y)². Hence if i < j, but z_i ≤ z_j, then swapping z_i and z_j reduces the sum of the squares. But we can return the order of the z_i to y_i by a sequence of swaps of this type: first swap 1 to the 1st place, then 2 to the 2nd place and so on. 

Problem A2

Let a₁ < a₂ < a₃ < ... be positive integers. Prove that for every i >= 1, there are infinitely many a_n that can be written in the form a_n = ra_i + sa_j, with r, s positive integers and j > i.

 

Solution

We must be able to find a set S of infinitely many a_n in some residue class mod a_i. Take a_j to be a member of S. Then for any a_n in S satisfying a_n > a_j, we have a_n = a_j + a multiple of a_i. 

Problem A3

Given any triangle ABC, construct external triangles ABR, BCP, CAQ on the sides, so that ∠PBC = 45^o, ∠PCB = 30^o, ∠QAC = 45^o, ∠QCA = 30^o, ∠RAB = 15^o, ∠RBA = 15^o. Prove that ∠QRP = 90^o and QR = RP.

 

Solution

Trigonometry provides a routine solution. Let BC = a, CA = b, AB = c. Then, by the sine rule applied to AQC, AQ = b/(2 sin 105^o) = b/(2 cos 15^o). Similarly, PB = a/(2 cos 15). Also AR = RB = c/(2 cos 15^o). So by the cosine rule RP² = (a² + c² - 2ac cos(B+60^o))/(4 cos²15^o), and RQ² = (b² + c² - 2bc cos(A+60^o))/(4 cos²15^o). So RP = RQ is equivalent to: a² - 2ac cos(60^o+B) = b² - 2bc cos(60^o+A) and hence to a² - ac cos B + √3 ac sin B = b² - bc cos A + √3 bc sin A. By the sine rule, the sine terms cancel. Also b - b cos A = a cos C, and a - c cos B = b cos C, so the last equality is true and hence RP = RQ. We get an exactly similar expression for PQ² and show that it equals 2 RP² in the same way.

A more elegant solution is to construct S on the outside of AB so that ABS is equilateral. Then we find that CAS and QAR are similar and that CBS and PBR are similar. So QR/CS = PR/CS. The ratio of the sides is the same in each case (CA/QA = CB/PB since CQA and CPB are similar), so QR = PR. Also there is a 45^o rotation between QAR and CAS and another 45^o rotation between CBS and PBR, hence QR and PR are at 90^o. 

Problem B1

Let A be the sum of the decimal digits of 4444⁴⁴⁴⁴, and B be the sum of the decimal digits of A. Find the sum of the decimal digits of B.

 

Solution

Let X = 4444⁴⁴⁴⁴.Then X has less than 4.4444 = 17776 digits, so A is at most 9.17776 = 159984. Hence B is at most 6.9 = 54. But all these numbers are congruent mod 9. 4444 = -2 (mod 9), so X = (-2)⁴⁴⁴⁴ (mod 9). But (-2)³ = 1 (mod 9), and 4444 = 1 (mod 3), so X = -2 = 7 (mod 9). But any number less than 55 and congruent to 7 has digit sum 7 (possibilities are 7, 16, 25, 34, 43, 52). Hence the answer is 7.

Problem B2

Find 1975 points on the circumference of a unit circle such that the distance between each pair is rational, or prove it impossible.

 

Solution

Let x be the angle cos^-14/5, so that cos x = 4/5, sin x = 3/5. Take points on the unit circle at angles 2nx for n integral. Then the distance between the points at angles 2nx and 2mx is 2 sin(n - m)x. The usual formula, giving sin(n - m)x in terms of sin x and cos x, shows that sin(n - m)x is rational. So it only remains to show that this process generates arbitarily many distinct points, in other words that x is not a rational multiple of π.

This is quite hard. There is an elegant argument in sections 5 and 8 of Hadwiger et al, Combinatorial geometry in the Plane. But we can avoid it by observing that there are only finitely many numbers with are nth roots of unity for n ≤ 2 x 1975, whereas there are infinitely many Pythagorean triples, so we simply pick a triple which is not such a root of unity. 

Problem B3

Find all polynomials P(x, y) in two variables such that:

(1)  P(tx, ty) = tⁿP(x, y) for some positive integer n and all real t, x, y;

(2)  for all real x, y, z: P(y + z, x) + P(z + x, y) + P(x + y, z) = 0;

(3)  P(1, 0) = 1.

 

Solution

(1) means that P is homogeneous of degree n for some n. Experimenting with low n, shows that the only solutions for n = 1, 2, 3 are (x - 2y), (x + y)(x - 2y), (x + y)²(x - 2y). It then obvious by inspection that (x + y)ⁿ(x - 2y) is a solution for any n. Taking x = y = z in (2) shows that P(2x,x) = 0, so (x - 2y) is always a factor. Taking x = y = 1, z = -2 gives P(1,-1) (2ⁿ - 2) = 0, so (x + y) is a factor for n > 1. All this suggests (but does not prove) that the general solution is (x + y)ⁿ(x - 2y).

Take y = 1 - x, z = 0 in (2) and we get: P(x, 1-x) = -1 - P(1-x, x). In particular, P(0,1) = -2. Now take z = 1 - x - y and we get: P(1-x, x) + P(1-y, y) + P(x+y, 1-x-y) = 0 and hence f(x+y) = f(x) + f(y), where f(x) = P(1-x, x) - 1. By induction we conclude that, for any integer m and real x, f(mx) = mf(x). Hence f(1/s) = 1/s f(1) and f(r/s) = r/s f(1) for any integers r, s. But P(0,1) = -2, so f(1) = -3. So f(x) = -3x for all rational x. But f is continuous, so f(x) = -3x for all x. So set x = b/(a+b), where a and b are arbitrary reals (with a+b non-zero). Then P(a,b) = (a+b)ⁿP(1-x, x) = (a+b)ⁿ(-3b/(a+b) + 1) = (a+b)^n-1(a-2b), as claimed. [For a+b = 0, we appeal to continuity, or use the already derived fact that for n > 1, P(a,b) = 0.]

 Solutions are also available in:   Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.