25th USA Mathematical Olympiad 1996 Problems

25th USA Mathematical Olympiad 1996 Problems

A1.  Let k = 1^o. Show that 2 sin 2k + 4 sin 4k + 6 sin 6k + ... + 180 sin 180k = 90 cot k.

A2.  Let S be a set of n positive integers. Let P be the set of all integers which are the sum of one or more distinct elements of S. Show that we can find n subsets of P whose union is P such that if a, b belong to the same subset, then a ≤ 2b.

A3.  Given a triangle, show that we can reflect it in some line so that the area of the intersection of the triangle and its reflection has area greater than 2/3 the area of the triangle.

B1.  A type 1 sequence is a sequence with each term 0 or 1 which does not have 0, 1, 0 as consecutive terms. A type 2 sequence is a sequence with each term 0 or 1 which does not have 0, 0, 1, 1 or 1, 1, 0, 0 as consecutive terms. Show that there are twice as many type 2 sequences of length n+1 as type 1 sequences of length n.

B2.  D lies inside the triangle ABC. ∠BAC = 50^o. ∠DAB = 10^o, ∠DCA = 30^o, ∠DBA = 20^o. Show that ∠DBC = 60^o.

B3.  Does there exist a subset S of the integers such that, given any integer n, the equation n = 2s + s' has exactly one solution in S? For example, if T = {-3, 0, 1, 4), then there are unique solutions -3 = 2·0 - 3, -1 = 2·1 - 3, 0 = 2·0 + 0, 1 = 2·0 + 1, 2 = 0 + 2·1, 3 = 2·1 + 1, 4 = 2·0 + 4, 5 = 2·-3 + 1, but not for 6 = 2·1 + 4 = 2·-3 + 0, so T cannot be a subset of S.

Solution

25th USA Mathematical Olympiad 1996

Problem A1

Let k = 1^o. Show that 2 sin 2k + 4 sin 4k + 6 sin 6k + ... + 180 sin 180k = 90 cot k.

Solution

Multiply the expression by sin k. We have 2 sin 2nk sin k = cos(2n-1)k - cos(2n+1)k. So 2n sin 2nk sin k = n cos(2n-1)k - n cos(2n+1)k. Adding these equations for n = 1, 2, ... , 90 gives: 2 sin 2k + 4 sin 4k + 6 sin 6k + ... + 180 sin 180k = cos k + (2 - 1) cos 3k + (3 - 2) cos 5k + ... + (90 - 89) cos 179k - 90 cos 181k. Now cos 181k = - cos k, so the last term is + 90 cos k. The other terms sum to zero in pairs: cos k + cos 179k = 0, cos 3k + cos 177k = 0, ... , cos 89k + cos 91k = 0. Hence result. Problem A2

Let S be a set of n positive integers. Let P be the set of all integers which are the sum of one or more distinct elements of S. Show that we can find n subsets of P whose union is P such that if a, b belong to the same subset, then a ≤ 2b.

Solution

Let the members of S be a₁ < a₂ < ... < a_n. Let s_m = a₁ + a₂ + ... + a_m and put s₀ = 0. Let P_m = { s ∈ P : s_m-1 < s ≤ s_m } for m = 1, 2, ... , n. We claim that this partition works. It is sufficient to show that if b ∈ P_m then 2b > s_m (for then if a also belongs to P_m we have a ≤ s_m <= 2b).

Now since b > s_m-1, b must be a sum which includes some a_i with i ≥ m. So certainly b ≥ a_i ≥ a_m = s_m - s_m-1 > s_m - b. Hence 2b > s_m as required.

---

Problem A3

Given a triangle, show that we can reflect it in some line so that the area of the intersection of the triangle and its reflection has area greater than 2/3 the area of the triangle.

Solution

Let the triangle be ABC. Assume A is the largest angle. Let AD be the altitude. Assume AB ≤ AC, so that BD ≤ BC/2. If BD > BC/3, then reflect in AD. If B' is the reflection of B', then B'D = BD and the intersection of the two triangles is just ABB'. But BB' = 2BD > 2/3 BC, so ABB' has more than 2/3 the area of ABC.

If BD < BC/3, then reflect in the angle bisector of C. The reflection of A' is a point on the segment BD and not D. (It lies on the line BC because we are reflecting in the angle bisector. A'C > DC because ∠CAD < ∠CDA = 90^o. Finally, A'C ≤ BC because we assumed ∠B does not exceed ∠A). The intersection is just AA'C. But area AA'C/area ABC = CA'/CB > CD/CB ≥ 2/3.

---

Problem B1

A type 1 sequence is a sequence with each term 0 or 1 which does not have 0, 1, 0 as consecutive terms. A type 2 sequence is a sequence with each term 0 or 1 which does not have 0, 0, 1, 1 or 1, 1, 0, 0 as consecutive terms. Show that there are twice as many type 2 sequences of length n+1 as type 1 sequences of length n.

Solution

Let S be the set of sequences length n and T the set of sequences length n+1 beginning with 0. Define f: S → T as follows. Let the m+1th term of f(s) be the same as the mth term if the mth term of s is 0 and different if the mth term of s is 1. It is clear that f is a bijection. [Define its inverse g by g(t) has 0 as its mth term iff the mth and m+1th terms of t are the same.] Also f(s) includes 0, 0, 1, 1 or 1, 1, 0, 0 iff s includes 0, 1, 0. Hence the number of type 1 sequences in S is the same as the number of type 2 sequences in T. The same result holds if we take T to be sequences which begin with 1.

---

Problem B2

D lies inside the triangle ABC. ∠BAC = 50^o. ∠DAB = 10^o, ∠DCA = 30^o, ∠DBA = 20^o. Show that ∠DBC = 60^o.

Solution

Reflect A in the line BD to get A'. Let Z be the intersection of BD and AA'. Let BA' meet AC at X. Since ∠ABX = 2 ∠ABD = 40^o, and ∠BAX = 50^o, we have ∠BXA = 90^o. Now ∠DAA' = ∠BAA' - ∠DAB = ∠BAA' - 10^o. But ∠BAA' = 90^o - ∠DBA = 70^o, so ∠DAA' = 60^o.

Let BX meet CD at Y. ∠DYX = ∠YXC + ∠DCX = 90^o + 30^o = 120^o = 180^o - angle DAA', so DAA'Y is cyclic, so ∠A'YA = ∠A'DA = 2 ∠ZDA = 2(∠DBA + ∠DAB) = 60^o.

But ∠XYC = 90 - ∠DCA = 60^o, so C is the reflection of A in BX. Hence BC = BA, so ∠ACB = ∠BAC = 50^o. Hence ∠ABC = 80^o and ∠DBC = 80^o - ∠DBA = 60^o.

---

Problem B3

Does there exist a subset S of the integers such that, given any integer n, the equation n = 2s + s' has exactly one solution in S? For example, if T = {-3, 0, 1, 4), then there are unique solutions -3 = 2·0 - 3, -1 = 2·1 - 3, 0 = 2·0 + 0, 1 = 2·0 + 1, 2 = 0 + 2·1, 3 = 2·1 + 1, 4 = 2·0 + 4, 5 = 2·-3 + 1, but not for 6 = 2·1 + 4 = 2·-3 + 0, so T cannot be a subset of S.

Solution

Answer: yes.

We show how to choose S inductively. Suppose we have already chosen a₁, a₂, ... , a_n, but we do not yet have a solution for m ≥ 0. Take N so that all |a_i| < N. Now take a_n+1 = 5N + m, a_n+2 = -10N - m. This gives a solution for m: m = 2a_n+1 + a_n+2, but it does not duplicate any existing solutions, since |2a_n+2 + a_n+1|, |2a_n+1 + a_i|, |2a_n+2 + a_i|, |a_n+1 + 2a_i|, |a_n+2 + 2a_i| are all ≥ 3N, whereas all existing sums have absolute value < 3N. Similarly for m < 0, we may take a_n+1 = - 5N + m, a_n+2 = 10N - m.

Comment. The problem (and the opportunity) is that since positive and negative numbers are allowed |s| and |s'| can be arbitrarily large and still give n = 2s + s'. Compare the similar problem where S must be a subset of the non-negative integers and we require a unique solution n = 2s + s' for all non-negative n. In this case we can give S explicitly as all numbers with just the digits 0 and 1 in base 4. In fact, the same idea works for the case of all the integers, but it requires a little more work to show that -4 works as a number base.