5th USA Mathematical Olympiad 1976 Problems

5th USA Mathematical Olympiad 1976 Problems

1.  The squares of a 4 x 7 chess board are colored red or blue. Show that however the coloring is done, we can find a rectangle with four distinct corner squares all the same color. Find a counter-example to show that this is not true for a 4 x 6 board.

2.  AB is a fixed chord of a circle, not a diameter. CD is a variable diameter. Find the locus of the intersection of AC and BD.

3.  Find all integral solutions to a² + b² + c² = a²b².

4.  A tetrahedron ABCD has edges of total length 1. The angles at A (BAC etc) are all 90^o. Find the maximum volume of the tetrahedron.

5.  The polynomials a(x), b(x), c(x), d(x) satisfy a(x⁵) + x b(x⁵) + x²c(x⁵) = (1 + x + x² + x³ + x⁴) d(x). Show that a(x) has the factor (x -1).

Solution

5th USA Mathematical Olympiad 1976

Problem 1

The squares of a 4 x 7 chess board are colored red or blue. Show that however the coloring is done, we can find a rectangle with four distinct corner squares all the same color. Find a counter-example to show that this is not true for a 4 x 6 board.

Solution

A counter-example for 4 x 6 is:

R   B   R   B   R   B

R   B   B   R   B   R

B   R   R   B   B   R

B   R   B   R   R   B

Every column has two blue and two red squares and no two columns have the red squares in the same two rows or the blue squares in the same two rows, so there can be no rectangles. Suppose there is a counter-example for a 4 x 7 rectangle. Suppose it has three red squares in the first column. Then in those rows each remaining column can have at most one red square, so four remaining columns each have at least two blue squares in those three columns. Hence two of those columns have blue squares in the same two rows and hence a blue cornered rectangle. Contradiction. Similarly if there are three blue squares in the first column. So each column must have two red and two blue squares. But there are only 6 ways of choosing 2 items from 4, so two columns must have red squares in the same rows. Contradiction. Problem 2

AB is a fixed chord of a circle, not a diameter. CD is a variable diameter. Find the locus of the intersection of AC and BD.

Solution

Let the lines meet at X and suppose X lies outside the circle. ∠AXB = ∠AXD (same angle) = 180 deg - ∠XAD - ∠XDA = 90^o - ∠XDA (CD is a diameter, so angle CAD = 90^o) = 90^o - ∠BDA (same angle). But ∠BDA is constant, so ∠AXB is constant and hence X lies on a circle through A and B.

Let O be the center of the circle ABC and O' the center of the circle ABX. We have ∠AOB = 2 ∠ADB, ∠AO'B = 2 ∠AXB, so ∠AOB + ∠AO'B = 180^o. Hence ∠OAO' + ∠OBO' = 180^o. But ∠OAO' = ∠OBO', so ∠OAO' = 90^o. In other words, the circles are orthogonal.

If X lies inside the circle center O, then ∠AXB = ∠XAD + ∠XDA = ∠CAD + ∠ADB (same angles) = 90^o + ∠ADB (CD diameter). So X lies on the same circle.

Conversely, suppose X lies on the circle O'. Extend XA, XB to meet the circle center O at C and D respectively. If X lies outside the circle center O, assume C does not lie inside the circle center O' (if not use D). Then ∠CAD = ∠AXD + ∠ADX = ∠AXB + ∠ADB (same angles) = (∠AO'B + ∠AOB)/2 = 90^o. Hence CD is a diameter.

If X lies inside the circle O', then ∠ABX = 90^o + ∠ADB. But ∠AXB = ∠ADB + ∠XBD. So ∠CBD = ∠XBD = 90^o. Hence CD is a diameter.

---

Problem 3

Find all integral solutions to a² + b² + c² = a²b².

Solution

Answer: 0, 0, 0.

Squares must be 0 or 1 mod 4. Since the rhs is a square, each of the squares on the lhs must be 0 mod 4. So a, b, c are even. Put a = 2a₁, b = 2b₁, c = 2c₁. Then a₁² + b₁² + c₁² = square. Repeating, we find that a, b, c must each be divisible by an arbitrarily large power of 2. So they must all be zero.

---

Problem 4

A tetrahedron ABCD has edges of total length 1. The angles at A (BAC etc) are all 90^o. Find the maximum volume of the tetrahedron.

Solution

Answer: (5√2 - 7)/162.

Let the edges at A have lengths x, y, z. Then the volume is xyz/6 and the perimeter is x + y + z + √(x² + y²) + √(y² + z²) + √(z² + x²) = 1. By AM/GM we have x + y + z ≥ 3k, where k = (xyz)^1/3. Also x² + y² ≥ 2xy, so √(x² + y²) + √(y² + z²) + √(z² + x²) ≥ √(2xy) + √(2yx) + √(2zx). By AM/GM that is >= 3√2 k. So we have 1 ≥ 3(1 + √2) k. Hence k³ ≤ (5√2 - 7)/27. Hence the volume is at most (5√2 - 7)/162. This is achieved if x = y = z = (√2 - 1)/3. Then the other three sides are (2 - √2)/3 and the perimeter is 1.

---

Problem 5

The polynomials a(x), b(x), c(x), d(x) satisfy a(x⁵) + x b(x⁵) + x²c(x⁵) = (1 + x + x² + x³ + x⁴) d(x). Show that a(x) has the factor (x -1).

Solution

Take k to be a complex 5th root of 1, so that 1 + k + k² + k³ + k⁴ = 0. Putting x = k, k², k³, k⁴ in the given equation we get:

a(1) + k b(1) + k2c(1) = 0

a(1) + k2b(1) + k4c(1) = 0

a(1) + k3b(1) + k c(1) = 0

a(1) + k4b(1) + k3c(1) = 0

Multiplying by -k , -k², -k³, -k⁴ respectively, we get

-k a(1) - k2b(1) - k3c(1) = 0

-k2a(1) - k4b(1) - k c(1) = 0

-k3a(1) - k b(1) - k4c(1) = 0

-k4a(1) - k3b(1) - k2c(1) = 0

Adding all eight equations gives 5 a(1) = 0. Hence a(x) has the root x = 1 and hence the factor (x - 1).