14th USA Mathematical Olympiad 1985 Problems
1. Do there exist 1985 distinct positive integers such that the sum of their squares is a cube and the sum of their cubes is a square?
2. Find all real roots of the quartic x4 - (2N + 1)x2 - x + N2 + N - 1 = 0 correct to 4 decimal places, where N = 1010.
3. A tetrahedron has at most one edge longer than 1. What is the maximum total length of its edges?
4. A graph has n > 2 points. Show that we can find two points A and B such that at least [n/2] - 1 of the remaining points are joined to either both or neither of A and B.
5. 0 < a1 ≤ a2 ≤ a3 ≤ ... is an unbounded sequence of integers. Let bn = m if am is the first member of the sequence to equal or exceed n. Given that a19 = 85, what is the maximum possible value of a1 + a2 + ... + a19 + b1 + b2 + ... + b85?
Solution
14th USA Mathematical Olympiad 1985
Problem 1
Do there exist 1985 distinct positive integers such that the sum of their squares is a cube and the sum of their cubes is a square?
Solution
Answer: yes.
Take any n integers ai. Suppose that ∑ ai2 = b and ∑ ai3 = c. Now multiply each ai by b4c3. The sum of their squares becomes b9c6 which is a cube and the sum of their cubes becomes b12c10 which is a square. Problem 2
Find all real roots of the quartic x4 - (2N + 1)x2 - x + N2 + N - 1 = 0 correct to 4 decimal places, where N = 1010.
Solution
Answer: 99999.9984 and 100000.0016.
We can write the equation as (x2 - N - 1/2)2 = x + 5/4. For x < -5/4 the lhs is positive and the rhs is negative, so there are no roots with x < -5/4. If x lies between -5/4 and 0, then the lhs is obviously much larger than the rhs, so again there is no root. Thus there are no negative roots. Descartes' rule of signs (see below) tells us that there are at most 2 positive roots.
If x = 105, then the lhs is 1/4 and the rhs is much larger (approx 105). If x = 105 ± 1, then the lhs is (± 2 105 + 1/2)2 which is approximately 4 1010 and much larger than the rhs. So there is a root either side of 105. Put x = 105 ± k. Then we want (± 2k.105 + k2 - 1/2)2 = 105 + 5/4, or (4k2105 - 1)105 ± 2k(1-2k2 )105 - 5/4 = 0. So evidently we need approximately 4k2 = 10-5, or k = ± 0.0016. So it looks as though the roots are 105 ± 0.0016 = 99999.9984 and 100000.0016.
Put x = 105 ± 0.00155. Then (x2 - 1010 - 1/2)2 - x - 5/4 = (±310 - 1/2 + 0.001552)2 - 105± 0.00155 - 5/4 < 3112 - 105 < 0. Put x = 105 ± 0.00165, then (x2 - 1010 - 1/2)2 - x - 5/4 = (±330 -1/2 + 0.001652)2 - 105 ± 0.00165 - 5/4 > 3292 - 105 - 2 > 0. So indeed one root lies between 105 - 0.00165 and 105 - 0.00155 and the other root lies between 105 + 0.00155 and 105 + 0.00165.
Descartes' rule of signs.
This states that if the number of sign changes in the coefficients of the polynomial is d, then the number of positive roots is d or d less an even number. So, for example, if the polynomial is x5 + 14.3 x4 - 34 x2 - x + 3.2, then there are two sign changes (+14.3 to -34 and -1 to 3.2), so there are either 0 or 2 positive roots. Note that we ignore zero coefficients. If r is a positive root of p(-x) = 0, then -r is a negative root of p(x) = 0. So if we substitute -x for x in the polynomial and the number of sign changes is then d', then we can conclude that the number of negative roots of the polynomial is either d' or d' less an even number. With the example above we get -x5 + 14.3 x4 - 34 x2 + x + 3.2, which has 3 sign changes. So the polynomial has 1 or 3 negative roots.
The proof is not difficult. The key idea is to show that if k is a positive root, so that p(x) = (x - k) q(x), then (1) p(x) has at least one more sign change than q(x), and (2) the difference between the number of sign changes is odd (note that the signs of the constant coefficients of p(x) and q(x) are different).
A tetrahedron has at most one edge longer than 1. What is the maximum total length of its edges?
Solution
Answer: 5 + √3.
Suppose AB is the edge which may be longer than 1. Then if we rotate the triangle ACD about CD until A lies in the same plane as BCD and is on the opposite side of CD to B, then we maximise AB without changing any of the other side lengths. So the maximal configuration must be planar.
Now suppose we regard C and D as fixed and the other points as variable. Suppose CD = 2x (<= 1). Then A and B must both lie inside the circle center C radius 1 and inside the circle center D radius 1 and hence inside their intersection which is bounded by the two arcs XY (assuming they meet at X and Y). Obviously we maximise AC + AD + BC + BD by taking A at X and B at Y (or vice versa). We claim that that choice also maximises AB. Suppose that is true. Then it also maximises AC + AD + BC + BD + AB at 4 + 2(1 - x2)1/2. So we now have to vary CD to maximise 2x + 4 + 2(1 - x2)1/2. We show that x + (1 - x2)1/2 is increasing for x <= 1/2 and hence that the maximum is at x = 1/2. Put x = sin t. Then we have x + (1 - x2)1/2 = √2 sin(t + π/4) which is indeed increasing for x ≤ π/6.
It remains to prove the claim. Take the circle diameter XY. Then the two arcs both lie inside this circle. [Two circles intersect in at most two points, so each arc must lie entirely inside or entirely outside the circle center O and it obviously does not lie outside. ] But AB lies inside a chord of this circle The length of the chord cannot exceed the diameter of the circle (which is XY) and hence AB ≤ XY.
A graph has n > 2 points. Show that we can find two points A and B such that at least [n/2] - 1 of the remaining points are joined to either both or neither of A and B.
Solution
Consider the number of pairs (X, {Y, Z}), where X, Y, Z are distinct points such that X is joined to just one of Y, Z. If X is joined to just k points, then there are just k(n - 1 - k) ≤ (n - 1)2/4 such pairs (X, {Y, Z}). Hence in total there are at most n(n - 1)2/4 such pairs. But there are n(n - 1)/2 possible {Y, Z}. So we must be able to find one of them {A, B} which belongs to at most [ (n - 1)/2 ] such pairs. Hence there are at least n - 2 - [ (n - 1)/2 ] = [n/2] - 1 points X which are joined to both of A and B or to neither of A and B. [If confused by the [ ], consider n = 2m and n = 2m+1 separately! ]
0 < a1 ≤ a2 ≤ a3 ≤ ... is an unbounded sequence of integers. Let bn = m if am is the first member of the sequence to equal or exceed n. Given that a19 = 85, what is the maximum possible value of a1 + a2 + ... + a19 + b1 + b2 + ... + b85?
Solution
We show that the only possible value of the sum is 85.20 = 1700.
That is certainly the value if all ai = 85, for then all bj = 1 and so the sum is 19·85 + 85·1 = 85·20. Now consider the general case. Suppose that we increase some ai by 1 from k to k+1 (whilst preserving the property that ai is increasing, so we must have ai < ai+1 before the increase). The effect of the increase is to change bk+1 from i+1 to i, but not to change any other bj. This is obvious if ai-1 < ai and ai+1 > ai + 1. If ai-1 = ai, then before the change bk = i-1 (not i) and that is still true after the change. Equally, if ai = ai+1 after the change, then it is still true that bk+1 changes from i+1 to i. Thus the overall effect of the increase is not to change the sum of the ai plus the sum of the bj. But by a series of such changes we convert any initial sequence to all ai = 85.
Labels:
USAMO
Previous Article
