8th USA Mathematical Olympiad 1979 Problems

8th USA Mathematical Olympiad 1979 Problems

1.  Find all sets of 14 or less fourth powers which sum to 1599.

2.  N is the north pole. A and B are points on a great circle through N equidistant from N. C is a point on the equator. Show that the great circle through C and N bisects the angle ACB in the spherical triangle ABC (a spherical triangle has great circle arcs as sides).

3.  a₁, a₂, ... , a_n is an arbitrary sequence of positive integers. A member of the sequence is picked at random. Its value is a. Another member is picked at random, independently of the first. Its value is b. Then a third, value c. Show that the probability that a + b + c is divisible by 3 is at least 1/4.

4.  P lies between the rays OA and OB. Find Q on OA and R on OB collinear with P so that 1/PQ + 1/PR is as large as possible.

5.  X has n members. Given n+1 subsets of X, each with 3 members, show that we can always find two which have just one member in common.

Solution

8th USA Mathematical Olympiad 1979

Problem 1

Find all sets of 14 or less fourth powers which sum to 1599.

Solution

Answer: none.

The only 4th powers less than 1599 are 1, 16, 81, 256, 625, 1296 (7⁴ = 2401). Note that 1, 81, 625 = 1 mod 16 and 16, 256, 1296 = 0 mod 16. But 1599 = 15 mod 16, so it cannot be expressed as a sum of 14 or less fourth powers. Problem 2

N is the north pole. A and B are points on a great circle through N equidistant from N. C is a point on the equator. Show that the great circle through C and N bisects the angle ACB in the spherical triangle ABC (a spherical triangle has great circle arcs as sides).

Solution

Let S_A, S_B, S_N be the great circles through A and C, B and C, and N and C respectively. Let C' be the point directly opposite C on the sphere. Then any great circle through C also goes through C'. So, in particular, S_A, S_B and S_N go through C'.

Two great circles through C meet at the same angle at C and at C', so the spherical angles ACN and AC'N are equal. Now rotate the sphere through an angle 180^o about the diameter through N. Then great circles through N map into themselves, so C and C' change places (C is on the equator). Also A and B change places (they are equidistant from N). S^A must go into another great circle through C and C'. But since A maps to B, it must be S_B. Hence the spherical angle AC'N = angle BCN (since one rotates into the other). Hence ACN and BCN are equal.

---

Problem 3

a₁, a₂, ... , a_n is an arbitrary sequence of positive integers. A member of the sequence is picked at random. Its value is a. Another member is picked at random, independently of the first. Its value is b. Then a third, value c. Show that the probability that a + b + c is divisible by 3 is at least 1/4.

Solution

Let the prob of a value = 0, 1, 2 mod 3 be p, q, r respectively. So p + q + r = 1 and p, q, r are non-negative. If a = b mod 3, then to get a + b + c = 0 mod 3, we require c = a mod 3. So the prob of such events is p³ + q³ + r³. If the first two values are different mod 3, then the third must be different again, so the prob. is 6pqr. Thus we have to show that p³ + q³ + r³ + 6pqr >= 1/4.

1 = (p + q + r)³ = p³ + q³ + r³ + 6pqr + 3(p²q + pq² + p²r + pr² + q²r + qr²). So we have to show that (p²q + pq² + p²r + pr² + q²r + qr²) <= 1/4. Or p²(q + r) + p(q² + r²) + qr(q + r) <= 1/4, or p²(1 - p) + p(q + r)² + qr(q + r - 2p) ≤ 1/4, or p²(1 - p) + p(1 - p)² + qr(1 - 3p) = p(1 - p) + qr(1 - 3p) ≤ 1/4.

If p ≥ 1/3, then we maximise p(1 - p) + qr(1 - 3p) by taking qr = 0 and p = 1/2 to maximise p(1 - p). Thus the maximum is 1/4, achieved at p = 1/2, q = 1/2, r = 0 and p = 1/2, q = 0, r = 1/2. But because of the symmetry, there is no loss of generality in assuming that p ≥ q ≥ r, so p must be ≥ 1/3. So the maximum value is 1/4.

---

Problem 4

P lies between the rays OA and OB. Find Q on OA and R on OB collinear with P so that 1/PQ + 1/PR is as large as possible.

Solution

Let the line through P parallel to OA meet OB at C. Note that C is fixed. Let the line through C parallel to QR meet OP at D. D varies as Q varies. Triangles ODC, OPR are similar, so CD/PR = OD/OP. Also triangles OPQ and PDC are similar, so CD/PQ = DP/OP. Adding, CD/PR + CD/PQ = 1. Hence we maximise 1/PQ + 1/PR by making CD as small as possible. That is achieved by making angle CDP = 90^o and hence QR perpendicular to OP.

---

Problem 5

X has n members. Given n+1 subsets of X, each with 3 members, show that we can always find two which have just one member in common.

Solution

We use induction on n. The result is true for n < 5, because there are at most n distinct subsets of 3 elements. Suppose it is true for all sets X with < n members. Let X have n members and consider a collection of n+1 subsets with 3 members. If every member of X was in at most 3 of the subsets, there would be at most n subsets, so some member A is in at least 4 of the subsets. Suppose one of them is {A, B, C}. There are at least three others, so B (say) must be in at least two of the others. Suppose they are {A, B, D} and {A, B, E}. Now any other subset containing A must contain B, because otherwise it would have to contain C, D and E, which is impossible. Similarly, any other subset containing B must contain A. So suppose there are m subsets containing A and B. If {A, B, K} is such a subset, then K cannot belong to any other subsets (because if it also belonged to S, then S and {A, B, K} would have just one member in common). So consider the n-(m+2) people other than those who belong to sets of the type {A, B, K}. There can be at most n-m-2 subsets involving them. Hence at most n-2 in total. So the result is true for n.

Note that we do worse than n subsets if we allow any member to be in 4 subsets. But at least for n = 4m we can achieve n subsets. Just take m groups of 4 and take all subsets with 3 members of each group.