10th USA Mathematical Olympiad 1981 Problems

10th USA Mathematical Olympiad 1981 Problems

1.  Prove that if n is not a multiple of 3, then the angle π/n can be trisected with ruler and compasses.

2.  What is the largest number of towns that can meet the following criteria. Each pair is directly linked by just one of air, bus or train. At least one pair is linked by air, at least one pair by bus and at least one pair by train. No town has an air link, a bus link and a trian link. No three towns, A, B, C are such that the links between AB, AC and BC are all air, all bus or all train.

3.  Show that for any triangle, 3(√3)/2 ≥ sin 3A + sin 3B + sin 3C ≥ -2. When does equality hold?

4.  A convex polygon has n sides. Each vertex is joined to a point P not in the same plane. If A, B, C are adjacent vertices of the polygon take the angle between the planes PBA and PBC. The sum of the n such angles equals the sum of the n angles subtended at P by the sides of the polygon (such as the angle APB). Show that n = 3.

5.  Show that for any positive real x, [nx] ≥ ∑₁ⁿ [kx]/k.

Solution

10th USA Mathematical Olympiad 1981

Problem 1

Prove that if n is not a multiple of 3, then the angle p/n can be trisected with ruler and compasses.

Solution

The key is to use π/3. Since n and 3 are relatively prime we can find integers a and b such that 3a + nb = 1. Hence aπ/n + bπ/3 = π/(3n). So take a circle with arcs subtending π/n and π/3 at the center. Start at a point X on the circumference, mark off |a| arcs subtending π/n in one direction, then mark off |b| arcs subtending π/3 in the other direction. We end up at a point Y with XY subtending π/3n at the center. Problem 2

What is the largest number of towns that can meet the following criteria. Each pair is directly linked by just one of air, bus or train. At least one pair is linked by air, at least one pair by bus and at least one pair by train. No town has an air link, a bus link and a trian link. No three towns, A, B, C are such that the links between AB, AC and BC are all air, all bus or all train.

Solution

Answer: 4. [eg A and B linked by bus. C and D both linked to A and B by air and to each other by train.]

Suppose A is linked to three other towns by air. Let them be B, C, D. B has at most one other type of link. Suppose it is bus. Then B must be linked to C and D by bus. But now there is a problem with the CD link. If it is air, then A, C, D are all linked by air. If it is bus, then B, C, D are all linked by bus. If it is train, then C has links of all three types. So A cannot be linked to three others by air. Similarly it cannot be linked to three others by train, or to three others by bus. Since it has at most two types of link, it can be linked to at most 4 towns (2 by one type of link and 2 by another). So certainly there cannot be more than 5 towns.

Suppose 5 is possible. A must be linked to two towns by one type of link and two by another. Without loss of generality we may suppose A is linked to B and C by bus and to D and E by train. Now suppose BE is an air link. Then B cannot have a train link (or it will have all three). It cannot be linked to C by bus (or ABC is all bus), so BC must be air. Similarly, ED must be air (it cannot be train or ADE is all train, or bus because then E has air, bus and train). But now there is a problem with the CE link. It cannot be air (or BCE is all air). It cannot be train, because C already has air and bus links. It cannot be bus, because E already has train and air links. So BE cannot be an air link. So it must be a bus or train link. Without loss of generality, we may assume it is a bus link.

E has a bus and a train link, so it cannot have air links. It cannot be linked to D by train (or AED is all train). So ED must be bus. Now DB cannot be air (or D has air, train and bus). It cannot be bus (or DBE is all bus). So it must be train. So BC cannot be air (or B has train, bus and air). It cannot be bus (or ABC is all bus). So BC must be train. CD cannot be air (or C has air, bus and train). It cannot be train (or BCD is all train). So CD must be bus. Finally, CE cannot be air (or C has air, bus and train). It cannot be bus (or CDE is all bus). So CE must be train. So none of the links are air. Contradiction. Hence 5 towns is not possible. But 4 is, as given in the Answer above.

---

Problem 3

Show that for any triangle, 3(√3)/2 ≥ sin 3A + sin 3B + sin 3C ≥ -2. When does equality hold?

Solution

Answer: 1st inequality, A = B = 20^o, C = 140^o. 2nd inequality, A = 0^o, B = C = 90^o (which is degenerate).

For x between 0 and 180^o, sin 3x is negative iff 60^o < x < 120^o. So at most two angles x in a triangle can have sin 3x negative. Obviously sin 3x ≥ -1, so sin 3A + sin 3B + sin 3C ≥ -2. We can only get equality in the degenerate case A = 0^o, B = C = 90^o (or with the angles relabeled).

We can certainly achieve 3(√3)/2 as shown above. But 3(√3)/2 > 2, so we must have all three sines positive. [If only two are positive, then their sum is at most 2.]. sin 3x is positive for x < 60^o and x > 120^o. So one angle must be > 120^o. Assume, for definiteness, that A ≤ B < 60^o, C > 120^o. Put C' = C - 120^o. Then 3A + 3B + 3C' = 180^o. Now sin x is a concave function for 0 ≤ x ≤ 180^o, or - sin x is a convex function. So by Jensen's inequality -sin x - sin y - sin z ≥ 3 -sin(x + y + z)/3. Hence sin 3A + sin 3B + sin 3C ≤ 3 sin 60^o = 3(√3)/2.

---

Problem 4

A convex polygon has n sides. Each vertex is joined to a point P not in the same plane. If A, B, C are adjacent vertices of the polygon take the angle between the planes PBA and PBC. The sum of the n such angles equals the sum of the n angles subtended at P by the sides of the polygon (such as the angle APB). Show that n = 3.

Solution

n = 3 is certainly possible. For example, take ∠APB = ∠APC = ∠BPC = 90^o (so that the lines PA, PB, PC are mutually perpendicular). Then the three planes through P are also mutually perpendicular, so the two sums are both 270^o.

We show that n > 3 is not possible.

The sum of the n angles APB etc at P is less than 360^o. This is almost obvious. Take another plane which meets the lines PA, PB, PC etc at A', B', C', ... and so that the foot of the perpendicular from P to the plane lies inside the n-gon A'B'C' ... then as we move P down the perpendicular the angles A'PB' etc all increase. But when it reaches the plane their sum is 360^o. However, I do not immediately see how to make that rigorous. Instead, take any point O inside the n-gon ABC... . We have ∠PBA + ∠PBC > ∠ABC. Adding the n such equations we get ∑(180^o - APB) > ∑ ABC = (n - 2) 180^o. So ∑ APB < 360^o.

The sum of the n angles between the planes is at least (n - 2) 180^o. If we take a sphere center P. Then the lines PA, PB intersect it at A", B", ... which form a spherical polygon. The angles of this polygon are the angles between the planes. We can divide the polygon into n - 2 triangles. The angles in a spherical triangle sum to at least 180^o. So the angles in the spherical polygon are at least (n - 2) 180^o. So we have (n - 2) 180^o < 360^o and hence n < 4.

---

Problem 5

Show that for any positive real x, [nx] ≥ ∑₁ⁿ [kx]/k.

Solution

If x is an integer, then we have equality. So it is sufficient to prove the result for 0 < x < 1. The rhs only increases at x = a/b, where a, b are coprime positive integers with 1 ≤ b ≤ n, and 0 ≤ a ≤ b. So it is sufficient to consider x of this form. In fact we can assume 0 < a < b since the equality is obvious for x = 0 or 1. We may write:

a = q₁b + r₁

2a = q₂b + r₂

3a = q₃b + r₃

...

na = q_nb + r_n

with each 0 ≤ r_i < b.

Thus kx = q_k and we have to prove that q₁ + q₂/2 + ... + q_n/n ≤ q_n.

We claim that r₁, r₂, ... , r_b-1 is just a permutation of 1, 2, ... , b-1. For if r_i = r_j with i < j, then (j - i)a = (q_j - q_i)b, but a and b are coprime and j - i < b, so that is impossible. So we may use the rearrangement inequality to give r₁/1 + r₂/2 + ... + r_b-1/b-1 ≥ 1/1 + 2/2 + ... + (b-1)/(b-1) = b-1. The inequality remains true if we add some positive terms to the lhs, so we have r₁/1 + r₂/2 + ... + r_n/n ≥ b-1. Hence r₁/b + r₂/(2b) + ... + r_n/(nb) ≥ (b-1)/b.

So (q₁ + q₂/2 + ... + q_n/n) + (b-1)/b ≤ (q₁ + r₁/b) + (q₂ + r₂/(2b) ) + ... (q_n + r_n/(nb) ) = a/b + a/b + ... + a/b = na/b = (q_nb + r_n)/b ≤ q_n + (b-1)/b. Subtracting (b-1)/b from both sides gives the required result.

Comment. This is unusually hard for an early USAMO question.

The rearrangement inequality states that if we consider all possible sums a₁b₁ + a₂b₂ + ... + a_nb_n where we can permute the two sequences a_i and b_i separately, then we get the largest sum when they are sorted the same way and the smallest when they are oppositely sorted (one increasing and one decreasing).