32nd International Mathematical Olympiad 1991 Problems & Solutions

A1.  Given a triangle ABC, let I be the incenter. The internal bisectors of angles A, B, C meet the opposite sides in A', B', C' respectively. Prove that:     1/4 < AI·BI·CI/(AA'·BB'·CC') ≤ 8/27.

A2.  Let n > 6 be an integer and let a₁, a₂, ... , a_k be all the positive integers less than n and relatively prime to n. If     a₂ - a₁ = a₃ - a₂ = ... = a_k - a_k-1 > 0,

prove that n must be either a prime number or a power of 2.

A3.  Let S = {1, 2, 3, ... 280}. Find the smallest integer n such that each n-element subset of S contains five numbers which are pairwise relatively prime.

B1.  Suppose G is a connected graph with k edges. Prove that it is possible to label the edges 1, 2, ... , k in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is 1. [A graph is a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of edges belongs to at most one edge. The graph is connected if for each pair of distinct vertices x, y there is some sequence of vertices x = v₀, v₁, ... , v_m = y, such that each pair v_i, v_i+1 (0 ≤ i < m) is joined by an edge.]

B2.  Let ABC be a triangle and X an interior point of ABC. Show that at least one of the angles XAB, XBC, XCA is less than or equal to 30^o.

B3.  Given any real number a > 1 construct a bounded infinite sequence x₀, x₁, x₂, ... such that |x_i - x_j| |i - j|^a ≥ 1 for every pair of distinct i, j. [An infinite sequence x₀, x₁, x₂, ... of real numbers is bounded if there is a constant C such that |x_i| < C for all i.] 

Solutions

Problem A1

Given a triangle ABC, let I be the incenter. The internal bisectors of angles A, B, C meet the opposite sides in A', B', C' respectively. Prove that:

    1/4 < AI·BI·CI/(AA'·BB'·CC') ≤ 8/27.

Solution

Consider the areas of the three triangles ABI, BCI, CAI. Taking base BC we conclude that (area ABI + area CAI)/area ABC = AI/AA'. On the other hand, if r is the radius of the in-circle, then area ABI = AB.r/2 and similarly for the other two triangles. Hence AI/AA' = (CA + AB)/p, where p is the perimeter. Similarly BI/BB' = (AB + BC)/p and CI/CC' = (BC + CA)/p. But the arithmetic mean of (CA + AB)/p, (AB + BC)/p and (BC + CA)/p is 2/3. Hence their product is at most (2/3)³ = 8/27.

Let AB + BC - CA = 2z, BC + CA - AB = 2x, CA + AB - BC = 2y. Then x, y, z are all positive and we have AB = y + z, BC = z + x, CA = x + y. Hence (AI/AA')(BI/BB')(CI/CC') = (1/2 + y/p)(1/2 + z/p)(1/2 + x/p) > 1/8 + (x+y+z)/(4p) = 1/8 + 1/8 = 1/4. 

Problem A2

Let n > 6 be an integer and let a₁, a₂, ... , a_k be all the positive integers less than n and relatively prime to n. If   a₂ - a₁ = a₃ - a₂ = ... = a_k - a_k-1 > 0, prove that n must be either a prime number or a power of 2.

Solution

by anon

If n is odd, then 1 and 2 are prime to n, so all integers < n are prime to n, and hence is prime.

If n = 4k, then 2k-1 and 2k+1 are prime to n, so all odd integers < n are prime to n, and hence n must be a power of 2.

If n = 4k+2, then 2k+1 divides n, but 2k+3 and 2k+5 are prime to n. But if n > 6, then 2k+5 < n, so this cannot be a solution. 

Problem A3

Let S = {1, 2, 3, ... 280}. Find the smallest integer n such that each n-element subset of S contains five numbers which are pairwise relatively prime.

Solution

Answer: 217.

Let A be the subset of all multiples of 2, 3, 5 or 7. Then A has 216 members and every 5-subset has 2 members with a common factor. [To show that |A| = 216, let a_n be the number of multiples of n in S. Then a₂ = 140, a₃ = 93, a₅ = 56, a₆ = 46, a₁₀ = 28, a₁₅ = 18, a₃₀ = 9. Hence the number of multiples of 2, 3 or 5 = a₂ + a₃ + a₅ - a₆ - a₁₀ - a₁₅ + a₃₀ = 206. There are ten additional multiples of 7: 7, 49, 77, 91, 119, 133, 161, 203, 217, 259.]

Let P be the set consisting of 1 and all the primes < 280. Define:
A1 = {2·41, 3·37, 5·31, 7·29, 11·23, 13·19}
A2 = {2·37, 3·31, 5·29, 7·23, 11·19, 13·17}
A3 = {2··31, 3·29, 5·23, 7·19, 11·17, 13·13}
B1 = {2·29, 3·23, 5·19, 7·17, 11·13}
B2 = {2·23, 3·19, 5·17, 7·13, 11·11}

Note that these 6 sets are disjoint subsets of S and the members of any one set are relatively prime in pairs. But P has 60 members, the three As have 6 each, and the two Bs have 5 each, a total of 88. So any subset T of S with 217 elements must have at least 25 elements in common with their union. But 6·4 = 24 < 25, so T must have at least 5 elements in common with one of them. Those 5 elements are the required subset of elements relatively prime in pairs. 

Problem B1

Suppose G is a connected graph with k edges. Prove that it is possible to label the edges 1, 2, ... , k in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is 1.

[A graph is a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of edges belongs to at most one edge. The graph is connected if for each pair of distinct vertices x, y there is some sequence of vertices x = v₀, v₁, ... , v_m = y, such that each pair v_i, v_i+1 (0 ≤ i < m) is joined by an edge.]

Solution

The basic idea is that consecutive numbers are relatively prime.

We construct a labeling as follows. Pick any vertex A and take a path from A along unlabeled edges. Label the edges consecutively 1, 2, 3, ... as the path is constructed. Continue the path until it reaches a vertex with no unlabeled edges. Let B be the endpoint of the path. A is now guaranteed to have the gcd (= greatest common divisor) of its edges 1, because one of its edges is labeled 1. All the vertices between A and B are guaranteed to have gcd 1 because they have at least one pair of edges with consecutive numbers. Finally, either B has only one edge, in which case its gcd does not matter, or it is also one of the vertices between A and B, in which case its gcd is 1.

Now take any vertex C with an unlabeled edge and repeat the process. The same argument shows that all the new vertices on the new path have gcd 1. The endpoint is fine, because either it has only one edge (in which case its gcd does not matter) or it has already got gcd 1.

Repeat until all the edges are labeled. 

Problem B2

Let ABC be a triangle and X an interior point of ABC. Show that at least one of the angles XAB, XBC, XCA is less than or equal to 30^o.

Solution

By Marcin Mazur, University of Illinois at Urbana-Champaign

Let P, Q, R be the feet of the perpendiculars from X to BC, CA, AB respectively. Use A, B, C to denote the interior angles of the triangle (BAC, CBA, ACB). We have PX = BX sin XBC = CX sin(C - XCA), QX = CX sin XCA = AX sin(A - XAB), RX = AX sin XAB = BX sin(B - XBC). Multiplying: sin(A - XAB) sin(B - XBC) sin(C - XCA) = sin A sin B sin C.

Now observe that sin(A - x)/sin x = sin A cot x - cos A is a strictly decreasing function of x (over the range 0 to π), so if XAB, XBC and XCA are all greater than 30, then sin(A - 30) sin(B - 30^o) sin(C - 30^o) > sin³30^o = 1/8.

But sin(A - 30^o) sin(B - 30^o) = (cos(A - B) - cos(A + B - 60^o))/2 ≤ (1 - cos(A + B - 60^o))/2 = (1 - sin(C - 30^o))/2, since (A - 30^o) + (B - 30^o) + (C - 30^o) = 90^o. Hence sin(A - 30^o) sin(B - 30^o) sin(C - 30^o) ≤ 1/2 (1 - sin(C - 30^o)) sin(C - 30^o) = 1/2 (1/4 - (sin(C - 30^o) - 1/2)²) ≤ 1/8. So XAB, XBC, XCA cannot all be greater than 30^o.

By Jean-Pierre Ehrmann

P, Q, R as above. Area ABX + area BCX + area CAX = area ABC, so AB·XR + BC·XP + CA·XQ = 2 area ABC ≤ BC·AP ≤ BC(AX + XP). Hence AB·XR/AX + CA·XQ/AX ≤ BC.

Squaring and using (λ + μ)² ≥ 4 λμ, we have: BC² ≥ 4 AB·CA. XR·XQ/AX². Similarly: CA² ≥ 4 BC·AB·XP·XR/BX², and AB² ≥ 4 AB·BC·XQ·XP/CX².

Multiplying these three inequalities together gives: 1 ≥ 64 (XR/AX)²(XP/BX)²(XQ/CX)², and hence: (XR/AX) (XP/BX) (XQ/CX) ≤ 1/8, or sin XAB sin XBC sin XCA ≤ 1/8. So not all XAB, XBC, XCA are greater than 30^o.

Gerard Gjonej noted that the result follows almost immediately from the Erdos-Mordell inequality: XA + XB + XC ≥ 2(XP + XQ + XR). [For if all the angles are greater than 30, then XR/XA, XP/XB, XQ/XC are all greater than sin 30^o = 1/2.]. This result was notoriously hard to prove - Erdos hawked it around a large number of mathematicians before Mordell found a proof - but the proof now appears fairly innocuous, at least if you do not have to rediscover it:

Let R₁, Q₁ be the feet of the perpendiculars from P to AB, CA respectively. Similarly, let P₂, R₂ be the feet of the perpendiculars from Q to BC, AB, and Q₃, P₃ the feet of the perpendiculars from R to CA, BC. Then P₂P₃ is the projection of QR onto BC, so P₂P₃/QR ≤ 1. Similarly, Q₃Q₁/RP ≤ 1, and R₁R₂/PQ ≤ 1. Hence XA + XB + XC ≥ XA.P₂P₃/QR + XB·Q₃Q₁/RP + XC·R₁R₂/PQ  (*)

Now BPXR is cyclic, because BPX and XRB are both right angles. Hence angle BXR = angle BPR = angle RPP₃, so triangles XBR and PRP₃ are similar. Hence PP₃ = PR.XR/XB.

Similarly, QQ₁ = QP·XP/XC, RR₂ = RQ·XQ/XA, and PP₂ = PQ·XQ/XC, QQ₃ = QR·XR/XA, RR₁ = RP·XP/XB. Substituting into (*), we obtain:
XA + XB + XC ≥ XA( PQ/QR XQ/XC + PR/QR XR/XB ) + XB( QR/RP XR/XA + QP/RP XP/XC ) + XC( RP/PQ XP/XB + RQ/PQ XQ/XA ).

On the right hand side, the terms involving XP are: XP( QP/RP XB/XC + RP/PQ XC/XB ), which has the form XP (x + 1/x) and hence is at least 2 XP. Similarly for the terms involving XQ and XR. 

Problem B3

Given any real number a > 1 construct a bounded infinite sequence x₀, x₁, x₂, ... such that |x_n - x_m| |n - m|^a ≥ 1 for every pair of distinct n, m.

[An infinite sequence x₀, x₁, x₂, ... of real numbers is bounded if there is a constant C such that |x_n| < C for all n.]

Solution

By Marcin Mazur, University of Illinois at Urbana-Champaign

Let t = 1/2^a. Define c = 1 - t/(1 - t). Since a > 1, c > 0. Now given any integer n > 0, take the binary expansion n = ∑_i b_i 2ⁱ, and define x_n = 1/c ∑_bi>0 tⁱ. For example, taking n = 21 = 2⁴ + 2² + 2⁰, we have x₂₁ = (t⁴ + t² + t⁰)/c. We show that for any unequal n, m, |x_n - x_m| |n - m|^a ≥ 1. This solves the problem, since the x_n are all positive and bounded by (∑ tⁿ )/c = 1/(1 - 2t).

Take k to be the highest power of 2 dividing both n and m. Then |n - m| ≥ 2^k. Also, in the binary expansions for n and m, the coefficients of 2⁰, 2¹, ... , 2^k-1 agree, but the coefficients for 2^k are different. Hence c |x_n - x_m| = t^k + ∑_i>k y_i, where y_i = 0, tⁱ or - tⁱ. Certainly ∑_i>k y_i > - ∑_i>k tⁱ = t^k+1/(1 - t), so c |x_n - x_m| > t^k(1 - t/(1 - t)) = c t^k. Hence |x_n - x_m| |n - m|^a > t^k 2^ak = 1. 

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.