35th International Mathematical Olympiad 1994 Problems & Solutions

A1. Let m and n be positive integers. Let a₁, a₂, ... , a_m be distinct elements of {1, 2, ... , n} such that whenever a_i + a_j ≤ n for some i, j (possibly the same) we have a_i + a_j = a_k for some k. Prove that: (a₁ + ... + a_m)/m ≥ (n + 1)/2.

A2. ABC is an isosceles triangle with AB = AC. M is the midpoint of BC and O is the point on the line AM such that OB is perpendicular to AB. Q is an arbitrary point on BC different from B and C. E lies on the line AB and F lies on the line AC such that E, Q, F are distinct and collinear. Prove that OQ is perpendicular to EF if and only if QE = QF.

A3. For any positive integer k, let f(k) be the number of elements in the set {k+1, k+2, ... , 2k} which have exactly three 1s when written in base 2. Prove that for each positive integer m, there is at least one k with f(k) = m, and determine all m for which there is exactly one k.

B1. Determine all ordered pairs (m, n) of positive integers for which (n³ + 1)/(mn - 1) is an integer.

B2. Let S be the set of all real numbers greater than -1. Find all functions f from S into S such that f(x + f(y) + xf(y)) = y + f(x) + yf(x) for all x and y, and f(x)/x is strictly increasing on each of the intervals -1 < x < 0 and 0 < x.

B3. Show that there exists a set A of positive integers with the following property: for any infinite set S of primes, there exist two positive integers m in A and n not in A, each of which is a product of k distinct elements of S for some k ≥ 2.

Solutions

Problem A1

Let m and n be positive integers. Let a₁, a₂, ... , a_m be distinct elements of {1, 2, ... , n} such that whenever a_i + a_j ≤ n for some i, j (possibly the same) we have a_i + a_j = a_k for some k. Prove that:

(a₁ + ... + a_m)/m ≥ (n + 1)/2.

Solution

Take a₁ < a₂ < ... < a_m. Take k ≤ (m+1)/2. We show that a_k + a_m-k+1 ≥ n + 1. If not, then the k distinct numbers a₁ + a_m-k+1, a₂ + a_m-k+1, ... , a_k + a_m-k+1 are all ≤ n and hence equal to some a_i. But they are all greater than a_m-k+1, so each i satisfies m-k+2 ≤ i ≤ m, which is impossible since there are only k-1 available numbers in the range.

Problem A2

ABC is an isosceles triangle with AB = AC. M is the midpoint of BC and O is the point on the line AM such that OB is perpendicular to AB. Q is an arbitrary point on BC different from B and C. E lies on the line AB and F lies on the line AC such that E, Q, F are distinct and collinear. Prove that OQ is perpendicular to EF if and only if QE = QF.

Solution

Assume OQ is perpendicular to EF. Then ∠EBO = ∠EQO = 90^o, so EBOQ is cyclic. Hence ∠OEQ = ∠OBQ. Also ∠OQF = ∠OCF = 90^o, so OQCF is cyclic. Hence ∠OFQ = ∠OCQ. But ∠OCQ = ∠OBQ since ABC is isosceles. Hence ∠OEQ = ∠OFQ, so OE = OF, so triangles OEQ and OFQ are congruent and QE = QF.

Assume QE = QF. If OQ is not perpendicular to EF, then take E'F' through Q perpendicular to OQ with E' on AB and F' on AC. Then QE' = QF', so triangles QEE' and QFF' are congruent. Hence ∠QEE' = ∠QFF'. So CA and AB make the same angles with EF and hence are parallel. Contradiction. So OQ is perpendicular to EF.

Problem A3

For any positive integer k, let f(k) be the number of elements in the set {k+1, k+2, ... , 2k} which have exactly three 1s when written in base 2. Prove that for each positive integer m, there is at least one k with f(k) = m, and determine all m for which there is exactly one k.

Answer

2, 4, ... , n(n-1)/2 + 1, ... .

Solution

To get a feel, we calculate the first few values of f explicitly:

f(2) = 0, f(3) = 0

f(4) = f(5) = 1, [7 = 111]

f(6) = 2, [7 = 111, 11 = 1011]

f(7) = f(8) = f(9) = 3 [11 = 1011, 13 = 1101, 14 = 1110]

f(10) = 4 [11, 13, 14, 19 = 10011]

f(11) = f(12) = 5 [13, 14, 19, 21 = 10101, 22 = 10110]

f(13) = 6 [14, 19, 21, 22, 25 = 11001, 26 = 11010]

We show that f(k+1) = f(k) or f(k) + 1. The set for k+1 has the additional elements 2k+1 and 2k+2 and it loses the element k+1. But the binary expression for 2k+2 is the same as that for k+1 with the addition of a zero at the end, so 2k+2 and k+1 have the same number of 1s. So if 2k+1 has three 1s, then f(k+1) = f(k) + 1, otherwise f(k+1) = f(k). Now clearly an infinite number of numbers 2k+1 have three 1s, (all numbers 2^r + 2^s + 1 for r > s > 0). So f(k) increases without limit, and since it only moves up in increments of 1, it never skips a number. In other words, given any positive integer m we can find k so that f(k) = m.

From the analysis in the last paragraph we can only have a single k with f(k) = m if both 2k-1 and 2k+1 have three 1s, or in other words if both k-1 and k have two 1s. Evidently this happens when k-1 has the form 2ⁿ + 1. This determines the k, namely 2ⁿ + 2, but we need to determine the corresponding m = f(k). It is the number of elements of {2ⁿ+3, 2ⁿ+4, ... , 2ⁿ⁺¹+4} which have three 1s. Elements with three 1s are either 2ⁿ+2^r+2^s with 0 ≤ r < s < n, or 2ⁿ⁺¹+3. So there are m= n(n-1)/2 + 1 of them. As a check, for n = 2, we have k = 2²+2 = 6, m = 2, and for n = 3, we have k = 2³+2 = 10, m = 4, which agrees with the f(6) = 2, f(10) = 4 found earlier.

Problem B1

Determine all ordered pairs (m, n) of positive integers for which (n³ + 1)/(mn - 1) is an integer.

Answer

(1, 2), (1, 3), (2, 1), (2, 2), (2, 5), (3, 1), (3, 5), (5, 2), (5, 3).

Solution

We start by checking small values of n. n = 1 gives n³ + 1 = 2, so m = 2 or 3, giving the solutions (2, 1) and (3, 1). Similarly, n = 2 gives n³ + 1 = 9, so 2m-1 = 1, 3 or 9, giving the solutions (1, 2), (2, 2), (5, 2). Similarly, n = 3 gives n³ + 1 = 28, so 3m - 1 = 2, 14, giving the solutions (1, 3), (5, 3). So we assume hereafter that n > 3.

Let n³ + 1 = (mn - 1)h. Then we must have h = -1 (mod n). Put h = kn - 1. Then n³ + 1 = mkn² - (m + k)n + 1. Hence n² = mkn - (m + k). (*) Hence n divides m + k. If m + k ≥ 3n, then since n > 3 we have at least one of m, k ≥ n + 2. But then (mn - 1)(kn - 1) ≥ (n² + 2n - 1)(n - 1) = n³ + n² - 3n + 1 = (n³ + 1) + n(n - 3) > n³ + 1. So we must have m + k = n or 2n.

Consider first m + k = n. We may take m ≥ k (provided that we remember that if m is a solution, then so is n - m). So (*) gives n = m(n - m) - 1. Clearly m = n - 1 is not a solution. If m = n - 2, then n = 2(n - 2) - 1, so n = 5. This gives the two solutions (m, n) = (2, 5) and (3, 5). If m < n - 2 then n - m ≥ 3 and so m(n - m) - 1 ≥ 3m - 1 ≥ 3n/2 - 1 > n for n > 3.

Finally, take m + k = 2n. So (*) gives n + 2 = m(2n - m). Again we may take m ≥ k. m = 2n - 1 is not a solution (we are assuming n > 3). So 2n - m ≥ 2, and hence m(2n - m) ≥ 2m ≥ 2n > n + 2.

Problem B2

Let S be the set of all real numbers greater than -1. Find all functions f :S→S such that f(x + f(y) + xf(y)) = y + f(x) + yf(x) for all x and y, and f(x)/x is strictly increasing on each of the intervals -1 < x < 0 and 0 < x.

Answer

f(x) = -x/(x+1).

Solution

Suppose f(a) = a. Then putting x = y = a in the relation given, we get f(b) = b, where b = 2a + a². If -1 < a < 0, then -1 < b < a. But f(a)/a = f(b)/b. Contradiction. Similarly, if a > 0, then b > a, but f(a)/a = f(b)/b. Contradiction. So we must have a = 0.

But putting x = y in the relation given we get f(k) = k for k = x + f(x) + xf(x). Hence for any x we have x + f(x) + xf(x) = 0 and hence f(x) = -x/(x+1).

Finally, it is straightforward to check that f(x) = -x(x+1) satisfies the two conditions.

Thanks to Gerhard Woeginger for pointing out the error in the original solution and supplying this solution.

Problem B3

Show that there exists a set A of positive integers with the following property: for any infinite set S of primes, there exist two positive integers m in A and n not in A, each of which is a product of k distinct elements of S for some k ≥ 2.

Solution

Let the primes be p₁ < p₂ < p₃ < ... . Let A consists of all products of n distinct primes such that the smallest is greater than p_n. For example: all primes except 2 are in A; 21 is not in A because it is a product of two distinct primes and the smallest is greater than 3. Now let S = {p_i₁, p_i₂, ... } be any infinite set of primes. Assume that p_i₁ < p_i₂ < ... . Let n = i₁. Then p_i₁p_i₂ ... p_{i_n} is not in A because it is a product of n distinct primes, but the smallest is not greater than p_n. But p_i₂p_i₃ ... p_{i_n+1} is in A, because it is a product of n distinct primes and the smallest is greater than p_n. But both numbers are products of n distinct elements of S.

The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary Mathematics