23rd USA Mathematical Olympiad 1994 Problems

23rd USA Mathematical Olympiad 1994 Problems

1.  a₁, a₂, a₃, ... are positive integers such that a_n > a_n-1 + 1. Put b_n = a₁ + a₂ + ... + a_n. Show that there is always a square in the range b_n, b_n+1, b_n+2, ... , b_n+1-1.

2.  The sequence a₁, a₂, ... , a₉₉ has a₁ = a₃ = a₅ = ... = a₉₇ = 1, a₂ = a₄ = a₆ = ... = a₉₈ = 2, and a₉₉ = 3. We interpret subscripts greater than 99 by subtracting 99, so that a₁₀₀ means a₁ etc. An allowed move is to change the value of any one of the a_n to another member of {1, 2, 3} different from its two neighbors, a_n-1 and a_n+1. Is there a sequence of allowed moves which results in a_m = a_m+2 = ... = a_m+96 = 1, a_m+1 = a_m+3 = ... = a_m+95 = 2, a_m+97 = 3, a_n+98 = 2 for some m? [So if m = 1, we have just interchanged the values of a₉₈ and a₉₉.]

3.  The hexagon ABCDEF has the following properties: (1) its vertices lie on a circle; (2) AB = CD = EF; and (3) the diagonals AD, BE, CF meet at a point. Let X be the intersection of AD and CE. Show that CX/XE = (AC/CE)².

4.  x_i is a infinite sequence of positive reals such that for all n, x₁ + x₂ + ... + x_n ≥ √n. Show that x₁² + x₂² + ... + x_n² > (1 + 1/2 + 1/3 + ... + 1/n) / 4 for all n.

5.  X is a set of n positive integers with sum s and product p. Show for any integer N ≥ s, ∑( parity(Y) (N - sum(Y))Cs ) = p, where aCb is the binomial coefficient a!/(b! (a-b)! ), the sum is taken over all subsets Y of X, parity(Y) = 1 if Y is empty or has an even number of elements, -1 if Y has an odd number of elements, and sum(Y) is the sum of the elements in Y.

Solution

23rd USA Mathematical Olympiad 1994

Problem 1

a₁, a₂, a₃, ... are positive integers such that a_n > a_n-1 + 1. Put b_n = a₁ + a₂ + ... + a_n. Show that there is always a square in the range b_n, b_n+1, b_n+2, ... , b_n+1-1.

Solution

If the result fails then for some m we have b_n > m² and b_n+1 ≤ (m+1)². So b_n+1^1/2 - b_n^1/2 < 1. Thus it is sufficient to prove that b_n+1^1/2 - b_n^1/2 ≥ 1. Squaring, that is equivalent to a_n+1 ≥ 2b_n^1/2 + 1 or b_n^1/2 ≤ (a_n+1 - 1)/2.

We have a_n-1 <= a_n - 2. So b_n ≤ a_n + (a_n - 2) + (a_n - 4) - ... - (a_n - 2(n-1)). Adding extra terms to the rhs if necessary we get b_n = 1 + 3 + 5 + ... + a_n for a_n odd, or 2 + 4 + 6 + ... + a_n for a_n even. In the odd case there are (a_n + 1)/2 terms of average size (a_n + 1)/2 (group them in pairs working from the outside in), so the sum is (a_n + 1)²/4. In the even case there are a_n/2 terms of average size (a_n + 2)/2, so the sum is a_n(a_n + 2)/4. So in either case we have b_n ≤ (a_n + 1)²/4 and hence b_n^1/2 ≤ (a_n + 1)/2 ≤ (a_n+1 - 1)/2. Problem 2

The sequence a₁, a₂, ... , a₉₉ has a₁ = a₃ = a₅ = ... = a₉₇ = 1, a₂ = a₄ = a₆ = ... = a₉₈ = 2, and a₉₉ = 3. We interpret subscripts greater than 99 by subtracting 99, so that a₁₀₀ means a₁ etc. An allowed move is to change the value of any one of the a_n to another member of {1, 2, 3} different from its two neighbors, a_n-1 and a_n+1. Is there a sequence of allowed moves which results in a_m = a_m+2 = ... = a_m+96 = 1, a_m+1 = a_m+3 = ... = a_m+95 = 2, a_m+97 = 3, a_n+98 = 2 for some m? [So if m = 1, we have just interchanged the values of a₉₈ and a₉₉.]

Solution

This is a classic invariant problem. We strongly suspect that there is no sequence of moves (otherwise it would be too easy to find), so that we must prove there is no sequence. The standard approach is to look for some invariant which is not changed by the allowed moves, but which is different for the initial and desired final positions.

For each member a_i of the sequence let b_i =

0 if a_i = a_i+1,

1 if (a_i, a_i+1) = (1, 2) , (2, 3) or (3, 1)

-1 if (a_i, a_i+1) = (1, 3), (2, 1) or (3, 2).

We hope that b₁ + b₂ + ... + b₉₉will be a suitable invariant. Suppose we make an allowed move by changing a_i. That has the effect of changing just b_i-1 and b_i. If a_i-1 = a_i+1, then b_i-1 + b_i = 0, so the total of the b_j does not change. If a_i-1 does not equal a_i+1, then we cannot change a_i since it must be different from both. Thus allowed moves do not change b₁ + ... + b₉₉. So it is an invariant. We now check it is suitable. The initial value is + 3 (there are 49 pairs (1,2), 48 pairs (2,1), 1 pair (2,3) and 1 pair (3,1) total 49 - 48 + 1 + 1 = 3. But the desired final position has value -3 (it has 48 pairs (1, 2), 49 pairs (2, 1), 1 pair (1, 3) and 1 pair (3, 2), total 48 - 49 - 1 - 1 = - 3). So we cannot get from one to the other by allowed moves.

---

Problem 3

The hexagon ABCDEF has the following properties: (1) its vertices lie on a circle; (2) AB = CD = EF; and (3) the diagonals AD, BE, CF meet at a point. Let X be the intersection of AD and CE. Show that CX/XE = (AC/CE)².

Solution

Let the diagonals AD, BE, CF meet at Y. We show first that the triangles AEC, YED are similar. ∠ACE = ∠ADE (ACDE circle) = YDE (same angle). ∠AEB = ∠CED (AB = CD), so ∠AEB + ∠BEC = ∠CED + ∠BEC or ∠AEC = ∠YED. So AEC and YED are similar, so AC/CE = YD/DE.

We next show that AEC and CDY are similar. ∠AEC = ∠ADC (circle) = ∠CDY (same angle). ∠EAC = ∠EAD + ∠DAC = ∠ECD (circle) + ∠ECF (EF = CD) = ∠DCY. So AEC and CDY are similar. So AC/CE = CY/YD.

Hence (AC/CE)² = CY/DE. Finally we show that CXY and EXD are similar. That is almost obvious because CF is parallel to DE since CD = EF. Hence CY/DE = CX/XE, which gives the required result.

---

Problem 4

x_i is a infinite sequence of positive reals such that for all n, x₁ + x₂ + ... + x_n ≥ √n. Show that x₁² + x₂² + ... + x_n² > (1 + 1/2 + 1/3 + ... + 1/n) / 4 for all n.

Solution

Note that this is rather a weak inequality. Taking n = 1, we get x₁ >= 1, but (1 + 1/2 + 1/3 + ... + 1/30) < 4, so it is only for n > 30 that we need to consider x₂! Of course, weak inequalities can be awkward to prove.

For a + b constant, we minimise a² + b² by taking |a - b| as small as possible. So we suspect that the minimum value of x₁² + ... + x_n² is when x₁ = 1, x₂ = √2 - 1, x₃ = √3 - √2, x₄ = √4 - √3, ... (*). Note that √n - √(n-1) = 1/(√n + √(n-1) > 1/(2√n). So for the values (*) we have x₁² + ... + x_n² > (1 + 1/2 + 1/3 + ... + 1/n)/4. So it remains to show that the values (*) do indeed give the minimum.

We use Abel's partial summation formula (whose proof is trivial). Put y_n = √n - √(n-1), s_n = x₁ + x₂ + ... + x_n, t_n = y₁ + ... + t_n. So we assume s_n ≥ t_n. Note also that y₁ > y₂ > y₃ > ... . Then the partial summation formula is: ∑ x_iy_i = ∑ s_i(y_i - y_i+1) + s_ny_n+1 (where the sum is taken from 1 to n). We also have ∑ y_i² = ∑ t_i(y_i - y_i+1) + t_ny_n+1. But each term is not more than the corresponding term in the first equality, so ∑ y_i² ≤ ∑ x_iy_i.

Now Cauchy-Schwartz gives (∑ x_iy_i)² ≤ ∑ x_i² ∑ y_i². Hence ∑ y_i² ≤ ∑ x_i², as required.

---

Problem 5

X is a set of n positive integers with sum s and product p. Show for any integer N >= s, ∑( parity(Y) (N - sum(Y))Cs ) = p, where aCb is the binomial coefficient a!/(b! (a-b)! ), the sum is taken over all subsets Y of X, parity(Y) = 1 if Y is empty or has an even number of elements, -1 if Y has an odd number of elements, and sum(Y) is the sum of the elements in Y.

Solution

(∑ (-1)ⁿ binomial) with the sum over all subsets Y of a set X strongly suggests the principle of inclusion and exclusion.

Consider all sequences of length N ≥ s of 0s and 1s with a total of s 1s. We can regard positions 1, 2, ... , a₁ as block a₁, positions a₁ + 1, a₂ + 2, ... , a₁ + a₂ as block a₂, positions a₁+a₂ + 1, a₁+a₂ + 2, ... , a₁+a₂ + a₃ as block a₃, and so on up to a₁ + ... + a_n-1 + 1, ... a₁ + ... + a_n as block a_n. We are interested in sequences which have just one 1 in each block. Counting directly there are obviously just p such sequences.

But we can also take N' to be the total number of sequences of 0s and 1s with s 1s and N_Y to be the number with no 1s in block k for k in Y, where Y is a subset of X. Requiring one 1 in each block is equivalent to requiring no block to have no 1s. So the PIE gives that p = N' - N_Y for Y with one element + N_Y for Y with 2 elements and so on. N' = NCs and N_Y = (N - sum(Y))Cs, so we have p = ∑( parity(Y) (N - sum(Y))Cs ), which is the required relation.