28th International Mathematical Olympiad 1987 Problems & Solutions

A1. Let p_n(k) be the number of permutations of the set {1, 2, 3, ... , n} which have exactly k fixed points. Prove that the sum from k = 0 to n of (k p_n(k) ) is n!. [A permutation f of a set S is a one-to-one mapping of S onto itself. An element i of S is called a fixed point if f(i) = i.]

A2. In an acute-angled triangle ABC the interior bisector of angle A meets BC at L and meets the circumcircle of ABC again at N. From L perpendiculars are drawn to AB and AC, with feet K and M respectively. Prove that the quadrilateral AKNM and the triangle ABC have equal areas.

A3. Let x₁, x₂, ... , x_n be real numbers satisfying x₁² + x₂² + ... + x_n² = 1. Prove that for every integer k ≥ 2 there are integers a₁, a₂, ... , a_n, not all zero, such that |a_i| ≤ k - 1 for all i, and |a₁x₁ + a₂x₂ + ... + a_nx_n| ≤ (k - 1)√n/(kⁿ - 1).

B1. Prove that there is no function f from the set of non-negative integers into itself such that f(f(n)) = n + 1987 for all n.

B2. Let n be an integer greater than or equal to 3. Prove that there is a set of n points in the plane such that the distance between any two points is irrational and each set of 3 points determines a non-degenerate triangle with rational area.

B3. Let n be an integer greater than or equal to 2. Prove that if k² + k + n is prime for all integers k such that 0 ≤ k ≤ √(n/3), then k² + k + n is prime for all integers k such that 0 ≤ k ≤ n-2.

Solutions

Problem A1

1. Let p_n(k) be the number of permutations of the set {1, 2, 3, ... , n} which have exactly k fixed points. Prove ∑₀ⁿ (k p_n(k) ) = n!.

First Solution

We show first that the number of permutations of n objects with no fixed points is n!(1/0! - 1/1! + 1/2! - ... + (-1)ⁿ/n!). This follows immediately from the law of inclusion and exclusion: let N_i be the number which fix i, N_ij the number which fix i and j, and so on. Then N₀, the number with no fixed points, is n! - all N_i + all N_ij - ... + (-1)ⁿN_1...n. But N_i = (n-1)!, N_ij = (n-2)! and so on. So N₀ = n! ( 1 - 1/1! + ... + (-1)^r(n-r)!/(r! (n-r)!) + ... + (-1)ⁿ/n!) = n! (1/0! - 1/1! + ... + (-1)ⁿ/n!).

Hence the number of permutations of n objects with exactly r fixed points = no. of ways of choosing the r fixed points x no. of perms of the remaining n - r points with no fixed points = n!/(r! (n-r)!) x (n-r)! (1/0! - 1/1! + ... + (-1)^n-r/(n-r)! ). Thus we wish to prove that the sum from r = 1 to n of 1/(r-1)! (1/0! - 1/1! + ... + (-1)^n-r/(n-r)! ) is 1. We use induction on n. It is true for n = 1. Suppose it is true for n. Then the sum for n+1 less the sum for n is: 1/0! (-1)ⁿ/n! + 1/1! (-1)^n-1/(n-1)! + ... + 1/n! 1/0! = 1/n! (1 - 1)ⁿ = 0. Hence it is true for n + 1, and hence for all n.

Comment

This is a plodding solution. If you happen to know the result for no fixed points (which many people do), then it is essentially a routine induction.

Second solution

Count all pairs (x, s) where s is a permutation with x a fixed point of x. Clearly, if we fix x, then there are (n-1)! possible permutations s. So the total count is n!. But if we count the number of permutations s with exactly k fixed points, then we get the sum in the question.

Comment

This much more elegant solution is due to Gerhard Wöginger (email 24 Aug 99).

Problem A2

In an acute-angled triangle ABC the interior bisector of angle A meets BC at L and meets the circumcircle of ABC again at N. From L perpendiculars are drawn to AB and AC, with feet K and M respectively. Prove that the quadrilateral AKNM and the triangle ABC have equal areas.

Solution

by Gerhard Wöginger

AKL and AML are congruent, so KM is perpendicular to AN and area AKNM = KM.AN/2.
AKLM is cyclic (2 opposite right angles), so angle AKM = angle ALM and hence KM/sin BAC = AM/sin AKM (sine rule) = AM/sin ALM = AL.
ABL and ANC are similar, so AB.AC = AN.AL. Hence area ABC = 1/2 AB.AC sin BAC = 1/2 AN.AL sin BAC = 1/2 AN.KM = area AKNM.

Problem A3

Let x₁, x₂, ... , x_n be real numbers satisfying x₁² + x₂² + ... + x_n² = 1. Prove that for every integer k ≥ 2 there are integers a₁, a₂, ... , a_n, not all zero, such that |a_i| ≤ k - 1 for all i, and |a₁x₁ + a₂x₂ + ... + a_nx_n| ≤ (k - 1)√n/(kⁿ - 1).

Solution

This is an application of the pigeon-hole principle.

Assume first that all x_i are non-negative. Observe that the sum of the x_i is at most √n. [This is a well-known variant, (∑_1≤i≤n x_i)² ≤ n ∑_1≤i≤n x_i², of the AM-GM result. See, for example, Arthur Engel, Problem Solving Strategies, Springer 1998, p163, ISBN 0387982191].

Consider the kⁿ possible values of ∑_1≤i≤n b_ix_i, where each b_i is an integer in the range [0,k-1]. Each value must lie in the interval [0, k-1 √n]. Divide this into kⁿ-1 equal subintervals. Two values must lie in the same subinterval. Take their difference. Its coefficients are the required a_i. Finally, if any x_i are negative, solve for the absolute values and then flip signs in the a_i.

Comment

This solution is due to Gerhard Woeginger, email 24 Aug 99.

Problem B1

Prove that there is no function f from the set of non-negative integers into itself such that f(f(n)) = n + 1987 for all n.

Solution

We prove that if f(f(n)) = n + k for all n, where k is a fixed positive integer, then k must be even. If k = 2h, then we may take f(n) = n + h.

Suppose f(m) = n with m = n (mod k). Then by an easy induction on r we find f(m + kr) = n + kr, f(n + kr) = m + k(r+1). We show this leads to a contradiction. Suppose m < n, so n = m + ks for some s > 0. Then f(n) = f(m + ks) = n + ks. But f(n) = m + k, so m = n + k(s - 1) ≥ n. Contradiction. So we must have m ≥ n, so m = n + ks for some s ≥ 0. But now f(m + k) = f(n + k(s+1)) = m + k(s + 2). But f(m + k) = n + k, so n = m + k(s + 1) > n. Contradiction.

So if f(m) = n, then m and n have different residues mod k. Suppose they have r₁ and r₂ respectively. Then the same induction shows that all sufficiently large s = r₁ (mod k) have f(s) = r₂ (mod k), and that all sufficiently large s = r₂ (mod k) have f(s) = r₁ (mod k). Hence if m has a different residue r mod k, then f(m) cannot have residue r₁ or r₂. For if f(m) had residue r₁, then the same argument would show that all sufficiently large numbers with residue r₁ had f(m) = r (mod k). Thus the residues form pairs, so that if a number is congruent to a particular residue, then f of the number is congruent to the pair of the residue. But this is impossible for k odd.

A better solution by Sawa Pavlov is as follows

Let N be the set of non-negative integers. Put A = N - f(N) (the set of all n such that we cannot find m with f(m) = n). Put B = f(A).

Note that f is injective because if f(n) = f(m), then f(f(n)) = f(f(m)) so m = n. We claim that B = f(N) - f( f(N) ). Obviously B is a subset of f(N) and if k belongs to B, then it does not belong to f( f(N) ) since f is injective. Similarly, a member of f( f(N) ) cannot belong to B.

Clearly A and B are disjoint. They have union N - f( f(N) ) which is {0, 1, 2, ... , 1986}. But since f is injective they have the same number of elements, which is impossible since {0, 1, ... , 1986} has an odd number of elements.

Problem B2

Let n be an integer greater than or equal to 3. Prove that there is a set of n points in the plane such that the distance between any two points is irrational and each set of 3 points determines a non-degenerate triangle with rational area.

Solution

Let x_n be the point with coordinates (n, n²) for n = 1, 2, 3, ... . We show that the distance between any two points is irrational and that the triangle determined by any 3 points has non-zero rational area.

Take n > m. |x_n - x_m| is the hypoteneuse of a triangle with sides n - m and n² - m² = (n - m)(n + m). So |x_n - x_m| = (n - m)√(1 + (n+m)²). Now (n + m)² < (n + m)² + 1 < (n + m + 1)² = (n + m)² + 1 + 2(n + m), so (n + m)² + 1 is not a perfect square. Hence its square root is irrational. [For this we may use the classical argument. Let N' be a non-square and suppose √N' is rational. Since N' is a non-square we must be able to find a prime p such that p^2a+1 divides N' but p^2a+2 does not divide N' for some a ≥ 0. Define N = N'/p^2a. Then √N = (√N')/p^a, which is also rational. So we have a prime p such that p divides N, but p² does not divide N. Take √N = r/s with r and s relatively prime. So s²N = r². Now p must divide r, hence p² divides r² and so p divides s². Hence p divides s. So r and s have a common factor. Contradiction. Hence non-squares have irrational square roots.]

Now take a < b < c. Let B be the point (b, a²), C the point (c, a²), and D the point (c, b²). Area x_ax_bx_c = area x_ax_cC - area x_ax_bB - area x_bx_cD - area x_bDCB = (c - a)(c² - a²)/2 - (b - a)(b² - a²)/2 - (c - b)(c² - b²)/2 - (c - b)(b² - a²) which is rational.

Problem B3

Let n be an integer greater than or equal to 2. Prove that if k² + k + n is prime for all integers k such that 0 ≤ k ≤ √(n/3), then k² + k + n is prime for all integers k such that 0 ≤ k ≤ n - 2.

Solution

First observe that if m is relatively prime to b + 1, b + 2, ... , 2b - 1, 2b, then it is not divisible by any number less than 2b. For if c <= b, then take the largest j ≥ 0 such that 2^jc ≤ b. Then 2^j+1c lies in the range b + 1, ... , 2b, so it is relatively prime to m. Hence c is also. If we also have that (2b + 1)² > m, then we can conclude that m must be prime, since if it were composite it would have a factor ≤ √m.

Let n = 3r² + h, where 0 ≤ h < 6r + 3, so that r is the greatest integer less than or equal to √(n/3). We also take r ≥ 1. That excludes the value n = 2, but for n = 2, the result is vacuous, so nothing is lost.

Assume that n + k(k+1) is prime for k = 0, 1, ... , r. We show by induction that N = n + (r + s)(r + s + 1) is prime for s = 1, 2, ... , n - r - 2. By the observation above, it is sufficient to show that (2r + 2s + 1)² > N, and that N is relatively prime to all of r + s + 1, r + s + 2, ... , 2r + 2s. We have (2r + 2s + 1)² = 4r² + 8rs + 4s² + 4r + 4s + 1. Since r, s ≥ 1, we have 4s + 1 > s + 2, 4s² > s², and 6rs > 3r. Hence (2r + 2s + 1)² > 4r² + 2rs + s² + 7r + s + 2 = 3r² + 6r + 2 + (r + s)(r + s + 1) >= N.

Now if N has a factor which divides 2r - i with i in the range -2s to r - s - 1, then so does N - (i + 2s + 1)(2r - i) = n + (r - i - s - 1)(r - i - s) which has the form n + s'(s'+1) with s' in the range 0 to r + s - 1. But n + s'(s' + 1) is prime by induction (or absolutely for s = 1), so the only way it can have a factor in common with 2r - i is if it divides 2r - i. But 2r - i ≤ 2r + 2s ≤ 2n - 4 < 2n and n + s'(s' + 1) ≥ n, so if n + s'(s' + 1) has a factor in common with 2r - i, then it equals 2r - i = s + r + 1 + s'. Hence s'² = s - (n - r - 1) < 0, which is not possible. So we can conclude that N is relatively prime to all of r + s + 1, ... , 2r + 2s and hence prime.

Read more