26th USA Mathematical Olympiad 1997 Problems

26th USA Mathematical Olympiad 1997 Problems

A1.  Let p_n be the nth prime. Let 0 < a < 1 be a real. Define the sequence x_n by x₀ = a, x_n = the fractional part of p_n/x_n-1 if x_n ≠ 0, or 0 if x_n-1 = 0. Find all a for which the sequence is eventually zero.

A2.  ABC is a triangle. Take points D, E, F on the perpendicular bisectors of BC, CA, AB respectively. Show that the lines through A, B, C perpendicular to EF, FD, DE respectively are concurrent.

A3.  Show that there is a unique polynomial whose coefficients are all single decimal digits which takes the value n at -2 and at -5.

B1.  A sequence of polygons is derived as follows. The first polygon is a regular hexagon of area 1. Thereafter each polygon is derived from its predecessor by joining two adjacent edge midpoints and cutting off the corner. Show that all the polygons have area greater than 1/3.

B2.  Show that xyz/(x³ + y³ + xyz) + xyz/(y³ + z³ + xyz) + xyz/(z³ + x³ + xyz) ≤ 1 for all positive real x, y, z.

B3.  The sequence of non-negative integers c₁, c₂, ... , c₁₉₉₇ satisfies c₁ ≥ 0 and c_m + c_n ≤ c_m+n <= c_m + c_n + 1 for all m, n > 0 with m + n < 1998. Show that there is a real k such that c_n = [nk] for 1 ≤ n ≤ 1997.

Solution

26th USA Mathematical Olympiad 1997

Problem A1

Let p_n be the nth prime. Let 0 < a < 1 be a real. Define the sequence x_n by x₀ = a, x_n = the fractional part of p_n/x_n-1 if x_n ≠ 0, or 0 if x_n-1 = 0. Find all a for which the sequence is eventually zero.

Solution

Let {x} denote the fractional part of x. {x} = x minus some integer, so {x} is rational iff x is rational. Hence if x_n is irrational, then p_n+1/x_n is irrational and hence x_n+1 is irrational. So if a is irrational, then the sequence is never zero.

Suppose x_n = r/s with 0 < r < s relatively prime integers. Then x_n+1 = u/r, where u is the remainder on dividing sp_n+1 by r. So, when expressed as a fraction in lowest terms, the denominator of x_n+1 is less than that for x_n. So if a is rational and has denominator b, then after at most b iterations we get zero.

Comment: the fact that the p_n are primes is a red herring. Problem A2

ABC is a triangle. Take points D, E, F on the perpendicular bisectors of BC, CA, AB respectively. Show that the lines through A, B, C perpendicular to EF, FD, DE respectively are concurrent.

Solution

Suppose that the feet of the perpendiculars from A and P to EF are H and K respectively. Then AF² - AE² = (AH² + FH²) - (AH² + EH²) = FH² - EH² = (FH + EH)(FH - EH) = FE(FH - EH). Similarly, PF² - PE² = FE(FK - EK). So H and K coincide iff AF² - AE² = PF² - PE². In other words, P lies on the line through A perpendicular to EF iff PF² - PE² = AF² - AE².

Thus if P is the intersection of the line through A perpendicular to EF and the line through B perpendicular to FD, then PF² - PE² = AF² - AE² and PD² - PF² = BD² - BF². Hence PD² - PE² = AF² - BF² + BD² - AE². But F is equidistant from A and B, so AF² = BF². Similarly, BD² = CD² and AE² = CE². Hence PD² - PE² = CD² - CE², so P also lies on the perpendicular to DE through C.

---

Problem A3

Show that there is a unique polynomial whose coefficients are all single decimal digits which takes the value n at -2 and at -5.

Solution

Call the polynomial p(x) = p₀ + p₁x + p₂x² + ... + p_mx^m. Since p(x) - n = 0 has -2 and -5 as roots, it must have the factor (x + 2)(x + 5) = x² + 7x + 10. So for some a₀, a₁, a₂, ... we have:

10a0              +n = p0 ∈ {0,1,2,3,4,5,6,7,8,9}

10a1 + 7a0           = p1 ∈ {0,1,2,3,4,5,6,7,8,9}

10a2 + 7a1 + a0      = p2 ∈ {0,1,2,3,4,5,6,7,8,9}

10a3 + 7a2 + a1      = p3 ∈ {0,1,2,3,4,5,6,7,8,9}

...

10ar+1 + 7ar + ar-1  = pr+1 ∈ {0,1,2,3,4,5,6,7,8,9}

...

Now these equations uniquely determine a_i and p_i. For p₀ must be chosen so that p₀ - n is a multiple of 10, which fixes p₀ and a₀ uniquely. Similarly, given p_i and a_i for 0 ≤ i ≤ r, we have p_r+1 = 10a_r+1 + 7a_r + a_r-1 = 7a_r + a_r-1 mod 10, so p_r+1 is uniquely determined and hence also a_r+1. Thus any solution is certainly unique, but it is not clear that the process terminates, so that p_i and a_i are zero from some point on. Evidently the sequence a_i is bounded. For if a_i, a_i+1 ≤ B ≥ 9, then |a_i+2| ≤ 0.7B + 0.1B + 0.1B ≤ B. So if we take B = max(9,|a₀|,|a₁|), then |a_i| ≤ B for all i.

So we can define L_k = min(a_k, a_k+1, a_k+2, ...), U_k = max(a_k, a_k+1, a_k+2, ... ). Obviously, we have L₀ ≤ L₁ ≤ ... ≤ L_k ≤ L_k+1 ≤ ... ≤ U_k+1 ≤ U_k ≤ ... ≤ U₁ ≤ U₀. So L_i is an increasing integer sequence which is bounded above, so we must have L_i = L for all sufficiently large i. Similarly, U_i = U for all sufficiently large i, and L ≤ U (1).

But if a_i, a_i+1 ≥ L, then a_i+2 ≤ -0.7L - 0.1L + 0.9 ≤ -0.8L + 0.9. So U ≤ -0.8L + 0.9 (2). Similarly, if a_i, a_i+1 ≤ U, then a_i+2 ≥ -0.8U, so L ≥ -0.8U (3).

But as the diagram shows the only lattice point satisfying (1), (2), (3) is (0,0), so a_i = 0 for all sufficiently large i, which establishes existence.  

---

Problem B1

A sequence of polygons is derived as follows. The first polygon is a regular hexagon of area 1. Thereafter each polygon is derived from its predecessor by joining to adjacent edge midpoints and cutting off the corner. Show that all the polygons have area greater than 1/3.

Solution

The first point to observe is that each polygon in the sequence is convex. The next point is that we can never completely eliminate the sides of the hexagon, in other words every polygon in the sequence has a vertex on each of the sides of the hexagon.

Let the hexagon be ABCDEF. The diagonals AC, BD, CE, DF, EA, FB meet at the six vertices of a smaller hexagon. Call it UVWXYZ. To be specific, let U be the intersection of FB and AC, V the intersection of AC and BD, W the intersection of BD and CE and so on. Now take any polygon in the sequence. It has a vertex on AB and a vertex on BC. Since it is convex, it must also include the segment joining these points. But any such segment intersects BU and BV. So it has a point on BU and on BV. Similarly for each of the other segments: CV, CW, DW, DX, ... . But the convex hull of these 12 points includes the hexagon UVWXYZ. Hence the area of any polygon in the sequence is at least that of UVWXYZ.

The triangle ABF is isosceles with angle ABF = 30 deg, so if AB = k, then BF = k√3. But BU = FZ = k/√3. Hence UZ = k√3 - 2k/√3 = k/√3. So the area of UVWXYZ is 1/3 the area of ABCDEF.

---

Problem B2

Show that xyz/(x³ + y³ + xyz) + xyz/(y³ + z³ + xyz) + xyz/(z³ + x³ + xyz) ≤ 1 for all real positive x, y, z.

Solution

For positive x, y, x ≥ y iff x² ≥ y², so (x - y)(x² - y²) ≥ 0, or x³ + y³ ≥ xy(x + y). Hence x³ + y³ + xyz ≥ xy(x + y + z) and so xyz/(x³ + y³ + xyz) ≤ z/(x + y + z). Adding the two similar equations gives the required inequality.

---

Problem B3

The sequence of non-negative integers c₁, c₂, ... , c₁₉₉₇ satisfies c₁ ≥ 0 and c_m + c_n ≤ c_m+n ≤ c_m + c_n + 1 for all m, n > 0 with m + n < 1998. Show that there is a real k such that c_n = [nk] for 1 ≤ n ≤ 1997.

Solution

Any such k must satisfy c_n/n ≤ k < c_n/n + 1/n for all n. Hence we must have c_m/m < c_n/n + 1/n or n c_m < m c_n + m for all m, n. Conversely, if this inequality holds, then such k exist. For example, we could take k = max c_n/n.

It is tempting to argue that n c_m < (n-1) c_m + c_2m < (n-2) c_m + c_3m < ... < c_mn ≤ c_mn-n + c_n + 1 ≤ ... ≤ m c_n + m. But this does only works for small m, n, because otherwise mn may be out of range. Instead we use induction on m+n. It is obviously true for m = n = 1 and indeed any m = n. Now suppose m < n (and it is true for smaller m + n). Then by induction (n - m) c_m < m c_n-m + m. But c_m ≤ c_n - c_n-m, so m c_m ≤ m c_n - m c_n-m. Adding, we get n c_m < m c_n + m as required. Similarly, if m > n (and the result is true for smaller m + n), then by induction, n c_m-n < (m - n) c_n + (m - n). But n c_m <= n c_n + n c_m-n + n, so adding n c_m < m c_n + m, as required.