21th USA Mathematical Olympiad 1992 Problems

21th USA Mathematical Olympiad 1992 Problems

1.  Let a_n be the number written with 2ⁿ nines. For example, a₀ = 9, a₁ = 99, a₂ = 9999. Let b_n = ∏₀ⁿ a_i. Find the sum of the digits of b_n.

2.  Let k = 1^o. Show that ∑₀⁸⁸ 1/(cos nk cos(n+1)k ) = cos k/sin²k.

3.  A set of 11 distinct positive integers has the property that we can find a subset with sum n for any n between 1 and 1500 inclusive. What is the smallest possible value for the second largest element?

4.  Three chords of a sphere are meet at a point X inside the sphere but are not coplanar. A sphere through an endpoint of each chord and X touches the sphere through the other endpoints and X. Show that the chords have equal length.

5.  A complex polynomial has degree 1992 and distinct zeros. Show that we can find complex numbers z_n, such that if p₁(z) = z - z₁ and p_n(z) = p_n-1(z)² - z_n, then the polynomial divides p₁₉₉₂(z).

Solution

21th USA Mathematical Olympiad 1992

Problem 1

Let a_n be the number written with 2ⁿ nines. For example, a₀ = 9, a₁ = 99, a₂ = 9999. Let b_n = P₀ⁿ a_i. Find the sum of the digits of b_n.

Solution

Answer: 9·2ⁿ.

Induction on n. We have b₀ = 9, digit sum 9, and b₁ = 891, digit sum 18, so the result is true for n = 0 and 1. Assume it is true for n-1. Obviously a_n < 10 to the power of 2ⁿ, so b_n-1 < 10 to the power of (1 + 2 + 2² + ... + 2^n-1) < 10 to the power of 2ⁿ. Now b_n = b_n-110^N - b_n-1, where N = 2ⁿ. But b_n-1 < 10^N, so b_n = (b_n-1 - 1)10^N + (10^N - b_n-1) and the digit sum of b_n is just the digit sum of (b_n-1 - 1)10^N plus the digit sum of (10^N - b_n-1).

Now b_n-1 is odd and so its last digit is non-zero, so the digit sum of b_n-1 - 1 is one less than the digit sum of b_n-1, and hence is 9·2^n-1 - 1. Multiplying by 10^N does not change the digit sum. (10^N - 1) - b_n-1 has 2ⁿ digits, each 9 minus the corresponding digit of b_n-1, so its digit sum is 9·2ⁿ - 9·2^n-1. b_n-1 is odd, so its last digit is not 0 and hence the last digit of (10^N - 1) - b_n-1 is not 9. So the digit sum of 10^N - b_n-1 is 9·2ⁿ - 9·2^n-1 + 1. Hence b_n has digit sum (9·2^n-1 - 1) + (9·2ⁿ - 9·2^n-1 + 1) = 9·2ⁿ. Problem 2

Let k = 1^o. Show that S₀⁸⁸ 1/(cos nk cos(n+1)k ) = cos k/sin²k.

Solution

tan(n+1)k - tan nk = ( sin(n+1)k cos nk - sin nk cos(n+1)k )/( cos nk cos(n+1)k ) = sin k /( cos nk cos(n+1)k ). Using this expression the sum telescopes and we get ∑₀⁸⁸ 1/(cos nk cos(n+1)k ) = (tan 89k - tan 0)/sin k. But tan 0 = 0 and tan 89k = cot(π/2 - 89k) = cot k.

---

Problem 3

A set of 11 distinct positive integers has the property that we can find a subset with sum n for any n between 1 and 1500 inclusive. What is the smallest possible value for the second largest element?

Solution

Answer: 248.

By taking the integers to be 1, 2, 4, 8, ... , 1024 we can generate all integers up to 2047. But by taking some integers smaller, we can do better. For example, 1, 2, 4, ... , 128, 247, 248, 750 gives all integers up to 1500. We can obviously use the integers 1, 2, 4, ... , 128 to generate all integers up to 255. Adding 248 gives all integers from 256 up to 503. Then adding 247 gives all integers from 504 to 750. So adding 750 gives all integers up to 1500. We show that we cannot do better than this.

Let the integers be a₁ < a₂ < ... < a₁₁. Put s_n = a₁ + ... + a_n. Take N such that s_N-1 < 1500 ≤ s_N. Note that 1500 must be a sum of some of the integers so certainly 1500 ≤ s₁₁. Equally we obviously have a₁ = 1, a₂ = 2, so N is well-defined and we have 1 < N ≤ 11. Now if 1 < k ≤ N, we have s_k-1 < 1500 and hence s_k-1 + 1 ≤ 1500. So some sum of distinct a_i must equal s_k-1 + 1 and it must involve an a_i with i > k-1 since s_k-1 < s_k-1 + 1. Hence a_k ≤ s_k-1 + 1 for 1 < k ≤ N.

Now an easy induction gives s_k ≤ 2_k - 1. We must have a₁ = 1 and hence s₁ = 1, so it is true for k = 1. Suppose it is true for k-1. Then a_k ≤ s_k-1 + 1 ≤ 2^k-1, so s_k = s_k-1 + a_k ≤ 2^k-1 - 1 + 2^k-1 = 2^k - 1, so it is true for k. Hence for all k ≤ N. But 2¹⁰ -1 = 1023 < 1500, so if N < 11, then s_N < 1500. Contradiction. Hence N = 11.

We have s_k = s_k-1 + a_k ≤ 2s_k-1 + 1. Hence s_k-1 ≥ (s_k - 1)/2. So s₁₁ ≥ 1500 implies s₁₀ ≥ 750. But s₈ ≤ 255, so a₉ + a₁₀ ≥ 495, so a₁₀ ≥ 248.

---

Problem 4

Three chords of a sphere are meet at a point X inside the sphere but are not coplanar. A sphere through an endpoint of each chord and X touches the sphere through the other endpoints and X. Show that the chords have equal length.

Solution

Let two of the chords be AB and CD. Take the plane containing them. In this plane we have a circle through A, B, C, D, and a circle through A, C, X which touches a circle through B, D, X at X. We show that AX = CX. Let the common tangent at X meet the larger circle at E and F. [Assume the points are in the order A, C, F, B, D, E as we go round the circle.] We have ∠XAC = ∠BAC (same angle) = ∠BDC (circle ABCD) = ∠BXF (XF tangent to BXD) = ∠EXA (opposite angle) = ∠XCA (EX tangent to AXC). So XAC is isosceles. So XA = XC. Similarly XB = XD. Hence AB = CD.

Similarly, the other pairs of chords are equal.

---

Problem 5

A complex polynomial has degree 1992 and distinct zeros. Show that we can find complex numbers z_n, such that if p₁(z) = z - z₁ and p_n(z) = p_n-1(z)² - z_n, then the polynomial divides p₁₉₉₂(z).

Solution

Let the polynomial of degree 1992 be q(z). Suppose its roots are w₁, w₂, ... , w₁₉₉₂. Let S₁ = {w₁, ... , w₁₉₉₂}. We now define S₂ as follows. Let z₁ = (w₁ + w₂)/2 and take S₂ to be the set of all numbers (w - z₁)² with w in S₁. Note that w = w₁ and w = w₂ give the same number. It is possible that other pairs may also give the same number. But certainly |S₂| <= |S₁| - 1. We now repeat this process until we get a set with only one member. Thus if S_i has more than one member, then we take we take z_i to be an average of any two distinct members. Then we take S_i+1 to be the set of all (w - z_i)² with w in S_i. So after picking at most 1991 elements z_i we have a set S_N with only one member. Take z_N to be that one member, so that S_N+1 = {0}. Now if N < 1991, take the remaining z_i to be 0 until we reach z₁₉₉₂.

Now as we allow z to take the values in S:

p₁(z) = (z - z₁) takes 1992 possible values;

p₂(z) = (z - z₁)² - z₂ takes at most 1991 possible values;

p₃(z) = ( (z - z₁² - z₂)² - z₃ takes at most 1990 possible values;

p₄(z) = ( ( (z - z₁)² - z₂)² - z₃)² - z₄ takes at most 1989 possible values;

...

p₁₉₉₂(z) takes only the value 0.

So every root of q(z) is also a root of p₁₉₉₂(z). Hence q(z) must divide p₁₉₉₂(z).