12th USA Mathematical Olympiad 1983 Problems

12th USA Mathematical Olympiad 1983 Problems

1.  If six points are chosen sequentially at random on the circumference of a circle, what is the probability that the triangle formed by the first three is disjoint from that formed by the second three.

2.  Show that the five roots of the quintic a₅x⁵ + a₄x⁴ + a₃x³ + a₂x² + a₁x + a₀ = 0 are not all real if 2a₄² < 5a₅a₃.

3.  S₁, S₂, ... , S_n are subsets of the real line. Each S_i is the union of two closed intervals. Any three S_i have a point in common. Show that there is a point which belongs to at least half the S_i.

4.  Show that one can construct (with ruler and compasses) a length equal to the altitude from A of the tetrahedron ABCD, given the lengths of all the sides. [So for each pair of vertices, one is given a pair of points in the plane the appropriate distance apart.]

5.  Prove that an open interval of length 1/n in the real line contains at most (n+1)/2 rational points p/q with 1 ≤ q ≤ n.

Solution

12th USA Mathematical Olympiad 1983

Problem 1

If six points are chosen sequentially at random on the circumference of a circle, what is the probability that the triangle formed by the first three is disjoint from that formed by the second three.

Solution

Answer: 3/10.

Only the order is important. We are interested in permutations of 123456 where the 123 are together (allowing wrapping). wlog the 1 is in first position. So the triangles are disjoint in the cases 123xxx, 132xxx, 1xxx23, 1xxx32, 12xxx3, 13xxx2. So the probability is 6·6/5! = 3/10. Problem 2

Show that the five roots of the quintic a₅x⁵ + a₄x⁴ + a₃x³ + a₂x² + a₁x + a₀ = 0 are not all real if 2a₄² < 5a₅a₃.

Solution

Let the roots be r_i. If the condition holds, then 2 ∑ r_i < 5 ∑ r_ir_j. Expanding, 2 ∑ r_i² + 4 ∑ r_ir_j < 5 ∑ r_ir_j, or 2 ∑ r_i² < ∑ r_ir_j. But if r_i and r_j are real we have we have 2r_ir_j ≤ r_i² + r_j². So if all the roots are real, adding the 10 similar equations gives 2 ∑ r_ir_j ≤ 4 ∑ r_i². Contradiction. Hence not all the roots are real.

---

Problem 3

S₁, S₂, ... , S_n are subsets of the real line. Each S_i is the union of two closed intervals. Any three S_i have a point in common. Show that there is a point which belongs to at least half the S_i.

Solution

We can write S_i = [a_i, b_i] ∪ [c_i, d_i], where a_i ≤ b_i ≤ c_i <= d_i. Put a = max a_i, d = min d_i. Then a belongs to some S_h, and d belongs to some S_k. Suppose there is some S_i which does not contain a or d. Then b_i < a, so any point in S_i and S_h does not belong to [a_i, b_i]. Similarly c_i > b, so that any point in S_i and S_k does not belong to [c_i, d_i]. But that means that S_i, S_h and S_k cannot have a point in common. Contradiction. So every S_i must contain a or d. Hence either a or d belongs to at least half of them.

---

Problem 4

Show that one can construct (with ruler and compasses) a length equal to the altitude from A of the tetrahedron ABCD, given the lengths of all the sides. [So for each pair of vertices, one is given a pair of points in the plane the appropriate distance apart.]

Solution

Let the altitude from A be AH with H in the plane BCD. The plane normal to BC through A also contains H. Suppose it meets BC at X. Then HX and AX are both perpendicular to BC.

Since we have the side lengths we can construct a cardboard cutout of the tetrahedron: the base BCD and the face BCA next to it, also the face CDA' (and the face BDA", although we do not need it. If we folded along the lines BC, CD and BD, then A, A' and A" would become coincident and we would get the tetrahedron.) We have just shown that in the plane AH is a straight line perpendicular to BC (and meeting it at X). So we draw this line and also the line through A' perpendicular to CD, giving H as their point of intersection. Thus we have AH and HX and we know that in the tetrahedron AH is perpendicular to HX. So draw a circle diameter AX and take a circle center H radius HX meeting the circle at K. Then AK is the required length.

---

Problem 5

Prove that an open interval of length 1/n in the real line contains at most (n+1)/2 rational points p/q with 1 ≤ q ≤ n.

Solution

This is a variant on the familiar result that m+1 integers from {1, 2, ... , 2m} must include one which divides another. To prove that, take the largest odd divisor of each of the m+1 integers. That gives us m+1 odd numbers from {1, 3, ... , 2m-1}, so by the pigeonhole principle we must have some odd integer b twice. If the corresponding integers are 2^hb and 2^kb, then one must divide the other.

Now if 1≤ q ≤ n and 1 ≤ kq ≤ n, then |p/q - p'/kq| ≥ 1/kq ≥ 1/n. But we cannot have two such points in an open interval of length 1/n. Obviously we cannot have two points with the same denominator, so if n = 2m, there are at most m points and if n = 2m+1 there are at most m+1 points.