33th USA Mathematical Olympiad 2003Problem A1
Show that for each n we can find an n-digit number with all its digits odd which is divisible by 5n.
Induction on n. For n = 1 we have 5. So suppose N works for n. Consider the five n+1 digit numbers 10n + N, 3·10n + N, 5·10n + N, 7·10n, 9·10n. We may take out the common factor 5n to get the five numbers k, k + h, k + 2h, k + 3h, k + 4h, for some k and h = 2n+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.
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 AiAj. Suppose the points of intersection along this diagonal are (in order) P0 = Ai, P1, P2, ... , Pm = Aj. Suppose Pk is the intersection of AiAj with ArAs. Then using the quadrilateral AiArAjAs we deduce that P0Pk (= AiPk) is rational. Hence PhPk = P0Pk - P0Ph 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 sin2y = 1 - cos2y 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.
Given a sequence S1 of n+1 non-negative integers, a0, a1, ... , an we derive another sequence S2 with terms b0, b1, ... , bn, where bi is the number of terms preceding ai in S1 which are different from ai (so b0 = 0). Similarly, we derive S2 from S1 and so on. Show that if ai ≤ i for each i, then Sn = Sn+1.
Note that the derived sequence bi also satisfies bi ≤ i (since there are only i terms preceding bi). We show that bi ≥ ai for each i. That is obvious if ai = 0. If ai = k > 0, then since each of the first k terms (a0, a1, ... , ak-1) must be < k, we certainly have bi ≥ k.
Next we show that if bi = ai, then further iterations do not change term i. If bi = ai = 0, then none of the terms before ai differ from 0, so all the terms before bi are also 0. But that means the corresponding terms of the next iteration must also all be 0. If bi = ai = k > 0, then since a0, a1, ... , ak-1 all differ from ai, the remaining terms (if any) ak, ak+1, ... , ai-1 must all be the same as ai. But that implies that each of bk, bk+1, ... , bi-1 must also be k. Hence if the next iteration is c0, c1, ... then ci = 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.
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 = MC2.
If MB·MD = MC2, 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 = MF2.
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 = MC2.
Prove that for any positive reals x, y, z we have (2x+y+z)2(2x2 + (y+z)2) + (2y+z+x)2(2y2 + (z+x)2) + (2z+x+y)2(2z2 + (x+y)2) ≤ 8.
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/(2x2+(3-x)2) = (1/3) (x2+6x+9)/(x2-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.
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 20032003, show that it is always possible to make a sequence of moves ending with zeros at every vertex.
It is possible to get stuck, so the result is not trivial. For example:
1 10 0 1 1We 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 DWe 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 0So 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 1The 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 0Since 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