20th International Mathematical Olympiad 1978 Problems & Solutions

A1.  m and n are positive integers with m < n. The last three decimal digits of 1978^m are the same as the last three decimal digits of 1978ⁿ. Find m and n such that m + n has the least possible value.

A2.  P is a point inside a sphere. Three mutually perpendicular rays from P intersect the sphere at points U, V and W. Q denotes the vertex diagonally opposite P in the parallelepiped determined by PU, PV, PW. Find the locus of Q for all possible sets of such rays from P.

A3.  The set of all positive integers is the union of two disjoint subsets {f(1), f(2), f(3), ... }, {g(1), g(2), g(3), ... }, where f(1) < f(2) < f(3) < ..., and g(1) < g(2) < g(3) < ... , and g(n) = f(f(n)) + 1 for n = 1, 2, 3, ... . Determine f(240).

B1.  In the triangle ABC, AB = AC. A circle is tangent internally to the circumcircle of the triangle and also to AB, AC at P, Q respectively. Prove that the midpoint of PQ is the center of the incircle of the triangle.

B2.  {a_k} is a sequence of distinct positive integers. Prove that for all positive integers n, ∑_1≤k≤n a_k/k² ≥ ∑_1≤k≤n 1/k.

B3.  An international society has its members from six different countries. The list of members has 1978 names, numbered 1, 2, ... , 1978. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice the number of a member from his own country. 

Solutions 

Problem A1

m and n are positive integers with m < n. The last three decimal digits of 1978^m are the same as the last three decimal digits of 1978ⁿ. Find m and n such that m + n has the least possible value.

 

Solution

We require 1978^m(1978^n-m - 1) to be a multiple of 1000=8·125. So we must have 8 divides 1978^m, and hence m ≥ 3, and 125 divides 1978^n-m - 1.

By Euler's theorem, 1978^φ(125) = 1 (mod 125). φ(125) = 125 - 25 = 100, so 1978¹⁰⁰ = 1 (mod 125). Hence the smallest r such that 1978^r = 1 (mod 125) must be a divisor of 100 (because if it was not, then the remainder on dividing it into 100 would give a smaller r). That leaves 9 possibilities to check: 1, 2, 4, 5, 10, 20, 25, 50, 100. To reduce the work we quickly find that the smallest s such that 1978^s = 1 (mod 5) is 4 and hence r must be a multiple of 4. That leaves 4, 20, 100 to examine.

We find 978² = 109 (mod 125), and hence 978⁴ = 6 (mod 125). Hence 978²⁰ = 6⁵ = 36·91 = 26 (mod 125). So the smallest r is 100 and hence the solution to the problem is 3, 103. 

Problem A2

P is a point inside a sphere. Three mutually perpendicular rays from P intersect the sphere at points U, V and W. Q denotes the vertex diagonally opposite P in the parallelepiped determined by PU, PV, PW. Find the locus of Q for all possible sets of such rays from P.

 

Solution

Suppose ABCD is a rectangle and X any point inside, then XA² + XC² = XB² + XD². This is most easily proved using coordinates. Take the origin O as the center of the rectangle and take OA to be the vector a, and OB to be b. Since it is a rectangle, |a| = |b|. Then OC is -a and OD is -b. Let OX be c. Then XA² + XC² = (a - c)² + (a + c)² = 2a² + 2c² = 2b² + 2c² = XB² + XD².

Let us fix U. Then the plane k perpendicular to PU through P cuts the sphere in a circle center C. V and W must lie on this circle. Take R so that PVRW is a rectangle. By the result just proved CR² = 2CV² - CP². OC is also perpendicular to the plane k. Extend it to X, so that CX = PU. Then extend XU to Y so that YR is perpendicular to k. Now OY² = OX² + XY² = OX² + CR² = OX² + 2CV² - CP² = OU² - UX² + 2CV² - CP² = OU² - CP² + 2(OV² - OC²) - CP² = 3OU² - 2OP². Thus the locus of Y is a sphere. 

Problem A3

The set of all positive integers is the union of two disjoint subsets {f(1), f(2), f(3), ... }, {g(1), g(2), g(3), ... }, where f(1) < f(2) < f(3) < ..., and g(1) < g(2) < g(3) < ... , and g(n) = f(f(n)) + 1 for n = 1, 2, 3, ... . Determine f(240).

 

Solution

Let F = {f(1), f(2), f(3), ... }, G = {g(1), g(2), g(3), ... }, N_n = {1, 2, 3, ... , n}. f(1) ≥ 1, so f(f(1)) ≥ 1 and hence g(1) ≥ 2. So 1 is not in G, and hence must be in F. It must be the smallest element of F and so f(1) = 1. Hence g(1) = 2. We can never have two successive integers n and n+1 in G, because if g(m) = n+1, then f(something) = n and so n is in F and G. Contradiction. In particular, 3 must be in F, and so f(2) = 3.

Suppose f(n) = k. Then g(n) = f(k) + 1. So |N_f(k)+1 ∩ G| = n. But |N_f(k)+1 ∩ F| = k, so n + k = f(k) + 1, or f(k) = n + k - 1. Hence g(n) = n + k. So n + k + 1 must be in F and hence f(k+1) = n + k + 1. This so given the value of f for n we can find it for k and k+1.

Using k+1 each time, we get, successively, f(2) = 3, f(4) = 6, f(7) = 11, f(12) = 19, f(20) = 32, f(33) = 53, f(54) = 87, f(88) = 142, f(143) = 231, f(232) = 375, which is not much help. Trying again with k, we get: f(3) = 4, f(4) = 6, f(6) = 9, f(9) = 14, f(14) = 22, f(22) = 35, f(35) = 56, f(56) = 90, f(90) = 145, f(145) = 234. Still not right, but we can try backing up slightly and using k+1: f(146) = 236. Still not right, we need to back up further: f(91) = 147, f(148) = 239, f(240) = 388. 

Problem B1

In the triangle ABC, AB = AC. A circle is tangent internally to the circumcircle of the triangle and also to AB, AC at P, Q respectively. Prove that the midpoint of PQ is the center of the incircle of the triangle.

 

Solution

It is not a good idea to get bogged down in complicated formulae for the various radii. The solution is actually simple.

By symmetry the midpoint, M, is already on the angle bisector of A, so it is sufficient to show it is on the angle bisector of B. Let the angle bisector of A meet the circumcircle again at R. AP is a tangent to the circle touching AB at P, so ∠PRQ = ∠APQ = ∠ABC. Now the quadrilateral PBRM is cyclic because the angles PBR, PMR are both 90^o. Hence ∠PBM = ∠PRM = (∠PRQ)/2, so BM does indeed bisect angle B as claimed. 

Problem B2

{a_k} is a sequence of distinct positive integers. Prove that for all positive integers n, ∑₁ⁿ a_k/k² ≥ ∑₁ⁿ 1/k.

 

Solution

We use the general rearrangement result: given b₁ ≥ b₂ ≥ ... ≥ b_n, and c₁ ≤ c₂ ≤ ... ≤ c_n, if {a_i} is a permutation of {c_i}, then ∑ a_ib_i ≥ ∑ c_ib_i. To prove it, suppose that i < j, but a_i > a_j. Then interchanging a_i and a_j does not increase the sum, because (a_i - a_j)(b_i - b_j) ≥ 0, and hence a_ib_i + a_jb_j ≥ a_jb_i + a_ib_j. By a series of such interchanges we transform {a_i} into {c_i} (for example, first swap c₁ into first place, then c₂ into second place and so on).

Hence we do not increase the sum by permuting {a_i} so that it is in increasing order. But now we have a_i > i, so we do not increase the sum by replacing a_i by i and that gives the sum from 1 to n of 1/k. 

Problem B3

An international society has its members from six different countries. The list of members has 1978 names, numbered 1, 2, ... , 1978. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice the number of a member from his own country.

 

Solution

The trick is to use differences.

At least 6.329 = 1974, so at least 330 members come from the same country, call it C1. Let their numbers be a₁ < a₂ < ... < a₃₃₀. Now take the 329 differences a₂ - a₁, a₃ - a₁, ... , a₃₃₀ - a₁. If any of them are in C1, then we are home, so suppose they are all in the other five countries.

At least 66 must come from the same country, call it C2. Write the 66 as b₁ < b₂ < ... < b₆₆. Now form the 65 differences b₂ - b₁, b₃ - b₁, ... , b₆₆ - b₁. If any of them are in C2, then we are home. But each difference equals the difference of two of the original a_is, so if it is in C1 we are also home.

So suppose they are all in the other four countries. At least 17 must come from the same country, call it C3. Write the 17 as c₁ < c₂ < ... < c₁₇. Now form the 16 differences c₂ - c₁, c₃ - c₁, ... , c₁₇ - c₁. If any of them are in C3, we are home. Each difference equals the difference of two b_is, so if any of them are in C2 we are home. [For example, consider c_i - c₁. Suppose c_i = b_n - b₁ and c₁ = b_m - b₁, then c_i - c₁ = b_n - b_m, as claimed.]. Each difference also equals the difference of two a_is, so if any of them are in C1, we are also home. [For example, consider c_i - c₁, as before. Suppose b_n = a_j - a₁, b_m = a_k - a₁, then c_i - c₁ = b_n - b_m = a_j - a_k, as claimed.]

So suppose they are all in the other three countries. At least 6 must come from the same country, call it C4. We look at the 5 differences and conclude in the same way that at least 3 must come from C5. Now the 2 differences must both be in C6 and their difference must be in one of the C1, ... , C6 giving us the required sum.

Read more

Solutions are also available in     Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in   István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.