27th USA Mathematical Olympiad 1998 Problems

27th USA Mathematical Olympiad 1998 Problems

A1.  The sets {a₁, a₂, ... , a₉₉₉} and {b₁, b₂, ... , b₉₉₉} together contain all the integers from 1 to 1998. For each i, |a_i - b_i| = 1 or 6. For example, we might have a₁ = 18, a₂ = 1, b₁ = 17, b₂ = 7. Show that ∑₁⁹⁹⁹ |a_i - b_i| = 9 mod 10.

A2.  Two circles are concentric. A chord AC of the outer circle touches the inner circle at Q. P is the midpoint of AQ. A line through A intersects the inner circle at R and S. The perpendicular bisectors of PR and CS meet at T on the line AC. What is the ratio AT/TC?

A3.  The reals x₁, x₂, ... , x_n+1 satisfy 0 < x_i < π/2 and ∑₁ⁿ⁺¹ tan(x_i - π/4) ≥ n-1. Show that ∏₁ⁿ⁺¹ tan x_i ≥ nⁿ⁺¹.

B1.  A 98 x 98 chess board has the squares colored alternately black and white in the usual way. A move consists of selecting a rectangular subset of the squares (with boundary parallel to the sides of the board) and changing their color. What is the smallest number of moves required to make all the squares black?

B2.  Show that one can find a finite set of integers of any size such that for any two members the square of their difference divides their product.

B3.  What is the largest number of the quadrilaterals formed by four adjacent vertices of an convex n-gon that can have an inscribed circle?

Solution

27th USA Mathematical Olympiad 1998

Problem A1

The sets {a₁, a₂, ... , a₉₉₉} and {b₁, b₂, ... , b₉₉₉} together contain all the integers from 1 to 1998. For each i, |a_i - b_i| = 1 or 6. For example, we might have a₁ = 18, a₂ = 1, b₁ = 17, b₂ = 7. Show that ∑₁⁹⁹⁹ |a_i - b_i| = 9 mod 10.

Solution

If |a_i - b_i| = 6, then a_i and b_i have the same parity, so the set of such a_i and b_i contains an even number of odd numbers. But if |a_i - b_i| = 1, then a_i and b_i have opposite parity, so each such pair includes just one odd number. Hence if the number of such pairs is even, then the set of all such a_i and b_i also has an even number of odd numbers. But the total number of a_i and b_i which are odd is 999 which is odd. Hence the number of pairs with |a_i - b_i| = 1 must be odd, and hence the number of pairs with |a_i - b_i| = 6 must be even. Suppose it is 2k. Then ∑ |a_i - b_i| = (999 - 2k) 1 + 2k 6 = 999 + 10k = 9 mod 10. Problem A2

Two circles are concentric. A chord AC of the outer circle touches the inner circle at Q. P is the midpoint of AQ. A line through A intersects the inner circle at R and S. The perpendicular bisectors of PR and CS meet at T on the line AC. What is the ratio AT/TC?

Solution

We have AR·AS = AQ² = AQ/2 2AQ = AP·AC, so ARP and ACS are similar, so ∠ACS = ∠ARP, so PRSC is cyclic. Hence T must be the center of its circumcircle and must also lie on the perpendicular bisector of CP. Hence it must be the midpoint of CP. So CT = 3/8 CA and hence AT/TC = 5/3.

However, that is not quite all. If CS is parallel to PR, then their perpendicular bisectors coincide and both pass through A. So one could also regard A as a possible position for T.

---

Problem A3

The reals x₁, x₂, ... , x_n+1 satisfy 0 < x_i < π/2 and ∑₁ⁿ⁺¹ tan(x_i - π/4) ≥ n-1. Show that ∏₁ⁿ⁺¹ tan x_i ≥ nⁿ⁺¹.

Solution

Put t_i = tan(x_i - π/4). Then (1 + t_i)/(1 - t_i) = tan(π/4 + x_i - π/4) = tan x_i. So we wish to show that ∏(1 + t_i)/(1 - t_i) ≥ nⁿ⁺¹.

The given inequality is equivalent to 1 + t_i ≥ ∑_j≠i (1 - t_j). Using the AM/GM inequality, this implies that (1 + t_i)/n >= ∏_j≠i (1 - t_j)^1/n. Hence ∏ (1 + t_i)/nⁿ⁺¹ ≥ ∏_i ∏_j≠i (1 - t_j)^1/n = ∏ (1 - t_i).

---

Problem 4

A 98 x 98 chess board has the squares colored alternately black and white in the usual way. A move consists of selecting a rectangular subset of the squares (with boundary parallel to the sides of the board) and changing their color. What is the smallest number of moves required to make all the squares black?

Solution

Answer: 98.

There are 4·97 adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most 4 pairs, so we need at least 97 moves. However, we start with two corners one color and two another, so at least one rectangle must include a corner square. But such a rectangle can only fix two pairs, so at least 98 moves are needed.

It is easy to see that 98 suffice: take 49 1x98 rectangles (alternate rows), and 49 98x1 rectangles (alternate columns).

---

Problem B2

Show that one can find a finite set of integers of any size such that for any two members the square of their difference divides their product.

Solution

We find inductively a set with n elements satisfying the slightly stronger condition that if a and b are any two elements, then a - b divides both a and b. For n = 2, we may take {1, 2}. Suppose we have a set S for n. Let m be the lowest common multiple (or any multiple) of all the members of S. Now take the set {m + a: a ∈ S} ∪ {m} for n+1. A difference (m + a) - (m + b) = a - b divides a and b, hence also m, and hence m + a and m + b. A difference (m + a) - m = a divides a and m and hence also m + a.

---

Problem B3

What is the largest number of the quadrilaterals formed by four adjacent vertices of an convex n-gon that can have an inscribed circle?

Solution

Answer: [n/2].

Take a regular n-gon and slice off alternate corners (until [n/2] corners have been cut). Specifically, if the vertices are A₁, A₂, ... , A_n, then we slice off the corners at A₁, A₃, A₅, ... A_m, where m = n-1 if n is even, or n-2 if n is odd. At each corner A_i which we slice, we take the inscribed circle to the triangle A_i-1A_iA_i+1, draw a tangent to it parallel to A_i-1A_i+1 and cut along the tangent. This procedure shows that [n/2] can be achieved.

To show that it is optimal it is sufficient to show that if A, B, C, D, E are adjacent vertices of any polygon and ABCD has an inscribed polygon, then BCDE does not. Since ABCD has an inscribed polygon, AD + BC = AB + CD (if the inscribed circle touches at X on AB and Y on AD, then AX = AY. That and the three similar equations give the result). So if BCDE also has an inscribed polygon, then BE + CD = BC + DE. Hence (adding) AD + BE = AB + DE. But the diagonals AD and BE must meet at some point X. Then AD + BE = AX + XD + BX + XE = (AX + XB) + (DX + XE) > AB + DE. Contradiction.