### 33th USA Mathematical Olympiad 2003

**Problem A1**

Show that for each n we can find an n-digit number with all its digits odd which is divisible by 5^{n}.

**Solution**

Induction on n. For n = 1 we have 5. So suppose N works for n. Consider the five n+1 digit numbers 10^{n} + N, 3·10^{n} + N, 5·10^{n} + N, 7·10^{n}, 9·10^{n}. We may take out the common factor 5^{n} to get the five numbers k, k + h, k + 2h, k + 3h, k + 4h, for some k and h = 2^{n+1}. Since h is relatively prime to 5, the five numbers are all incongruent mod 5 and so one must be a multiple of 5. **Problem A2**

A convex polygon has all its sides and diagonals with rational length. It is dissected into smaller polygons by drawing all its diagonals. Show that the small polygons have all sides rational.

**Solution**

It is not hard to see that it is sufficient to prove the result for convex quadrilaterals. For in the case of an n-gon any side of a small polygon is either a side of the n-gon (in which case there is nothing to prove) or a segment of a diagonal. Suppose the diagonal is A_{i}A_{j}. Suppose the points of intersection along this diagonal are (in order) P_{0} = A_{i}, P_{1}, P_{2}, ... , P_{m} = A_{j}. Suppose P_{k} is the intersection of A_{i}A_{j} with A_{r}A_{s}. Then using the quadrilateral A_{i}A_{r}A_{j}A_{s} we deduce that P_{0}P_{k} (= A_{i}P_{k}) is rational. Hence P_{h}P_{k} = P_{0}P_{k} - P_{0}P_{h} is rational. So all the segments of the diagonal are rational.

It is immediate from the cosine rule that the angles in a triangle with rational sides have rational cosines. So cos x, cos y and cos(x+y) are rational (using triangles ABD, BCD, ADC). Using the formula for cos(x+y) it follows that sin x sin y is rational. Now sin^{2}y = 1 - cos^{2}y is rational, so sin x/sin y is rational.

Now area APD = (AD·PD sin x)/2 and area CPD = CD·PD sin y)/2, so AP/PC = area APD/area CPD = (sin x/sin y)(AD/CD) = rational. But AP + PC is rational, so AP is rational. Similarly for the other segments.

**Problem A3**

Given a sequence S_{1} of n+1 non-negative integers, a_{0}, a_{1}, ... , a_{n} we derive another sequence S_{2} with terms b_{0}, b_{1}, ... , b_{n}, where b_{i} is the number of terms preceding a_{i} in S_{1} which are different from a_{i} (so b_{0} = 0). Similarly, we derive S_{2} from S_{1} and so on. Show that if a_{i} ≤ i for each i, then S_{n} = S_{n+1}.

**Solution**

Note that the derived sequence b_{i} also satisfies b_{i} ≤ i (since there are only i terms preceding b_{i}). We show that b_{i} ≥ a_{i} for each i. That is obvious if a_{i} = 0. If a_{i} = k > 0, then since each of the first k terms (a_{0}, a_{1}, ... , a_{k-1}) must be < k, we certainly have b_{i} ≥ k.

Next we show that if b_{i} = a_{i}, then further iterations do not change term i. If b_{i} = a_{i} = 0, then none of the terms before a_{i} differ from 0, so all the terms before b_{i} are also 0. But that means the corresponding terms of the next iteration must also all be 0. If b_{i} = a_{i} = k > 0, then since a_{0}, a_{1}, ... , a_{k-1} all differ from a_{i}, the remaining terms (if any) a_{k}, a_{k+1}, ... , a_{i-1} must all be the same as a_{i}. But that implies that each of b_{k}, b_{k+1}, ... , b_{i-1} must also be k. Hence if the next iteration is c_{0}, c_{1}, ... then c_{i} = k also.

Now we use induction on k. Clearly term 0 is always 0. Considering the two cases, we see that term 1 does not change at iteration 1. So suppose that term i does not change at iteration i. If term i+1 does change at iteration i+1, then it must have changed at all previous iterations. So it must have started at 0 and increased by 1 at each iteration.

**Problem B1**

ABC is a triangle. A circle through A and B meets the sides AC, BC at D, E respectively. The lines AB and DE meet at F. The lines BD and CF meet at M. Show that M is the midpoint of CF iff MB·MD = MC^{2}.

**Solution**

If MB·MD = MC^{2}, then BM/MC = CM/MD, so triangles CMD and BMC are similar, so ∠MCD = ∠MBC. But ABED is cyclic, so ∠MBC = ∠DAE, so AE is parallel to CF. But now we can reverse the argument, but "reflecting" about BM so that we interchange A and E, and C and F, to conclude that MB·MD = MF^{2}.

Suppose conversely that MC = MF. Applying Ceva's theorem to triangle BCF, we have that (BA/AF)(1)(CE/EB) = 1, so BA/AF = BE/EC so AE is parallel to CF. We can now use the argument above to show that MB·MD = MC^{2}.

**Problem B2**

Prove that for any positive reals x, y, z we have (2x+y+z)^{2}(2x^{2} + (y+z)^{2}) + (2y+z+x)^{2}(2y^{2} + (z+x)^{2}) + (2z+x+y)^{2}(2z^{2} + (x+y)^{2}) ≤ 8.

**Solution**

If the inequality holds for x, y, z, then it also holds for kx, ky, kz, so it is sufficient to prove the result for x+y+z=3. The first term becomes (x+3)^{2}/(2x^{2}+(3-x)^{2}) = (1/3) (x^{2}+6x+9)/(x^{2}-2x+3) = (1/3) (1 + (8x+6)/(2+(x-1)^{2}) ≤ (1/3) (1 + (8x+6)/2) = 4/3 + 4x/3. Similarly for the other terms, so the whole expression ≤ (4/3 + 4x/3) + (4/3 + 4y/3) + (4/3 + 4z/3) = 8.

**Problem B3**

A positive integer is written at each vertex of a hexagon. A move is to replace a number by the (non-negative) difference between the two numbers at the adjacent vertices. If the starting numbers sum to 2003^{2003}, show that it is always possible to make a sequence of moves ending with zeros at every vertex.

**Solution**

It is possible to get stuck, so the result is not trivial. For example:

1 10 0 1 1

We show that provided the sum of the numbers is odd, we can always find a sequence of moves which give either (1) a lower maximum number, and odd sum, or (2) all zeros. Since the starting sum is odd, that is sufficient. Note that no move *increases* the maximum. The first step is to show that if the sum is odd, we can find moves which give just one number odd. For convenience we refer to the numbers as

A BF C E D

We also use the letters to refer to moves. So, for example, B means the move replacing B. Since the sum is odd, either A+C+E is odd or B+D+F is odd. wlog A+C+E is odd. Suppose just one of A,B,C is odd. wlog it is A. Making the moves B, F, A, F, D and working mod 2 we get successively: 1 B 1 1 1 1 0 1 0 1 0 1F 0 F 0 1 0 1 0 0 0 0 0 0 D 0 D 0 D 0 D 0 D 0 0

Similarly, if all of A, B, C are odd, then B, F, D, E, C we get mod 2:

1 B 1 0 1 0 1 0 1 0 1 0F 1 F 1 0 1 0 1 0 1 0 0 1 D 1 D 1 D 1 0 0 0 0 0

So wlog A is odd and all the other numbers are even. Suppose that the maximum is M. We show how to reduce M. There are two cases. Suppose first that M is even so that A < M. Then we make the moves B, C, D, E, F giving (mod 2): 1 0 1 1 1 1 1 1 1 1 1 10 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 1 1

The first four moves do not change A, which is neither 1 nor M, so the last move must reduce F, so the new maximum must be an odd number. But it must be ≤M, which is even, so the new maximum is <M and the sum is still odd. The second case is M odd, so that A = M. If C > 0 we make the moves B, F, A, F giving (mod 2):

1 0 1 1 1 1 0 1 0 10 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

Since C is not 0 or M, the new B must be <M and the other new numbers are all even and hence <M. So the new maximum is <M and the sum is still odd. The same argument works if E > 0 (just reflect about AD). So finally suppose C = E = 0. Then we get (no reduction mod 2): A B A A A A A A A A 0 A 0 A 0 0F 0 F 0 A 0 A 0 A 0 A 0 0 0 0 0 0 D 0 D 0 D 0 D 0 0 0 0 0 0 0 0