4th USA Mathematical Olympiad 1975 Problems

4th USA Mathematical Olympiad 1975 Problems

1.  Show that for any non-negative reals x, y, [5x] + [5y] ≥ [3x+y] + [x+3y]. Hence or otherwise show that (5a)! (5b)!/( a! b! (3a+b)! (a+3b)! ) is integral for any positive integers a, b.  

2.  Show that for any tetrahedron the sum of the squares of the lengths of two opposite edges is at most the sum of the squares of the other four.

3.  A polynomial p(x) of degree n satisfies p(0) = 0, p(1) = 1/2, p(2) = 2/3, ... , p(n) = n/(n+1). Find p(n+1).  

4.  Two circles intersect at two points, one of them X. Find Y on one circle and Z on the other, so that X, Y and Z are collinear and XY.XZ is as large as possible. 

5.  A pack of n cards, including three aces, is well shuffled. Cards are turned over in turn. Show that the expected number of cards that must be turned over to reach the second ace is (n+1)/2.  

Solution

4th USA Mathematical Olympiad 1975

Problem 1

Show that for any non-negative reals x, y, [5x] + [5y] ≥ [3x+y] + [x+3y]. Hence or otherwise show that (5a)! (5b)!/( a! b! (3a+b)! (a+3b)! ) is integral for any positive integers a, b.

Solution

If is obviously sufficient to prove that [5x] + [5y] ≥ [3x+y] + [x+3y] for 0 < x < y < 1. If 2x ≥ y, then [5x] ≥ [3x+y] and [5y] ≥ [x+3y], so the result holds. So assume 2x < y. It is now a question of examining a lot of cases.

If y < 2/5, then 3x + y < 5y/2 < 1, so [3x+y] = 0, and [3y+x] <= [5y], so the result holds. If 2/5 ≤ y < 3/5 and x < 1/5, then [5y] = 2, [3x+y] = 0 or 1 and [x+3y] = 1. If 2/5 ≤ y < 3/5 and x ≥ 1/5, the [5x]+[5y] = 3, [3x+y] = 1, [x+3y] = 1 or 2. If 3/5 ≤ y < 4/5, then [5y] = 3, [3x+y] = 0 or 1, [x+3y] = 2 or 3. If y ≥ 4/5 and x < 1/5, then [5x] + [5y] = 4, [3x+y] = 0 or 1, [x+3y]= 2 or 3. If y ≥ 4/5 and 1/5 ≤ x, then [5x] + [5y] = 5, [3x+y] = 2, [x+3y] = 2 or 3.

The highest power of a prime p dividing n! is [n/p] + [n/p²] + [n/p³] + ... . Thus it is sufficient to show that [5m/p] + [5n/p] ≥ [ (3m+n)/p ] + [ (m+3n)/p ], which follows immediately from the previous result, putting x = m/p, y = n/p. Problem 2

Show that for any tetrahedron the sum of the squares of the lengths of two opposite edges is at most the sum of the squares of the other four.

Solution

Let the vertices be A, B, C, D. We will show that AB² + CD² ≤ AC² + AD² + BC² + BD². Use vectors with origin A. Let the vectors from A to B, C, D be B, C, D respectively. We have to show that B² + (C - D)² ≤ C² + D² + (B - C)² + (B - D)². Rearranging, this is equivalent to (B - C - D)² ≥ 0. 

Problem 3

A polynomial p(x) of degree n satisfies p(0) = 0, p(1) = 1/2, p(2) = 2/3, ... , p(n) = n/(n+1). Find p(n+1).

Solution

The polynomial (x + 1)p(x) - x has degree n+1 and zeros at 0, 1, 2, ... , n, so it must be k x (x - 1)(x - 2) ... (x - n). Also it has value 1 at x = -1, so k (n+1)! (-1)ⁿ⁺¹. Hence (n+2) p(n+1) - (n+1) = (-1)ⁿ⁺¹. So for n odd, p(n+1) = 1, and for n even, p(n+1) = n/(n+2). 

Problem 4

Two circles intersect at two points, one of them X. Find Y on one circle and Z on the other, so that X, Y and Z are collinear and XY.XZ is as large as possible.

Solution

Let the circle through XY have center O and the other circle have center O'. XY = 2 OX sin XOY, XZ = 2 O'X sin XOZ, so we wish to maximise 2 sin XOY sin XO'Z. But 1/2 ∠XOY = 90^o - ∠OXY, 1/2 ∠XO'Z = 90^o - ∠OXZ, so 1/2 ∠XOY + 1/2 ∠XO'Z = ∠OXO', which is fixed. Thus ∠XOY + ∠XO'Z is fixed. But 2 sin XOY sin XO'Z = cos(XOY-XO'Z) - cos(XOY+XO'Z), so we maximise by taking XOY = XO'Z.

Note that in this case ∠OYZ = ∠O'ZY, so if we extend YO and ZO' to meet at C, then CY = CZ and hence C is the center of a circle containing the two circles and touching them at Y and Z. Also ∠CZY = ∠OXY, so O'Z is parallel to OX. Similarly OY is parallel to O'X, which shows how to construct Y and Z. 

Problem 5

A pack of n cards, including three aces, is well shuffled. Cards are turned over in turn. Show that the expected number of cards that must be turned over to reach the second ace is (n+1)/2.

Solution

For each arrangement A of the cards, let A' be the reflection about the middle of the pack, so that if a card is in position m in A, then it is in position (n+1-m) in A'. Then all possible arrangements can be grouped into pairs (A, A') (note that A cannot equal A'). If the position of the second ace in A is m, then it is n+1-m in A', so the average over A and A' is (n+1)/2. Hence that is also the average over all the arrangements.