﻿ 32nd USA Mathematical Olympiad 2003 | United States of America Mathematical Olympiad - USAMO | USA Mathematical Olympiad - USAMO
 Math Activities   User Guide   Help   Kids Math Books   Questions & Answers Search Math Resources - It's easy!
 more: Math Books | Math Activities
United States of America Mathematical Olympiad - USAMO

# United States of America Mathematical Olympiad - USAMO

32nd USA Mathematical Olympiad 2003 Problems
 A1.  Show that for each n we can find an n-digit number with all its digits odd which is divisible by 5n. 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. A3.  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. 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 = MC2. B2.  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. 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 20032003, show that it is always possible to make a sequence of moves ending with zeros at every vertex.

### 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 5n.

Solution

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.

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 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.

Problem A3

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.

Solution

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.

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 = MC2.

Solution

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.

Problem B2

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.

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/(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.

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 20032003, 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`

 Related Lessons in United States of America Mathematical Olympiad - USAMO Mathematical Olympiad
Division Lessons
 <<  Double division Dividing Fractions >>
Related subject
Common keywords: APMO, Chinese, Iberoamerican, Polish.
The text passage contains a series of mathematical problems and their solutions from the 32nd USA Mathematical Olympiad 2003. Each problem is presented with a detailed solution.
multiple_questions_with_answers
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
﻿ 32nd USA Mathematical Olympiad 2003 | United States of America Mathematical Olympiad - USAMO | USA Mathematical Olympiad - USAMO
 Math Activities   User Guide   Help   Kids Math Books   Questions & Answers Search Math Resources - It's easy!
 more: Math Books | Math Activities
United States of America Mathematical Olympiad - USAMO

# United States of America Mathematical Olympiad - USAMO

32nd USA Mathematical Olympiad 2003 Problems
 A1.  Show that for each n we can find an n-digit number with all its digits odd which is divisible by 5n. 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. A3.  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. 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 = MC2. B2.  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. 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 20032003, show that it is always possible to make a sequence of moves ending with zeros at every vertex.

### 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 5n.

Solution

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.

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 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.

Problem A3

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.

Solution

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.

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 = MC2.

Solution

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.

Problem B2

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.

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/(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.

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 20032003, 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`

 Related Lessons in United States of America Mathematical Olympiad - USAMO Mathematical Olympiad
Division Lessons
 <<  Double division Dividing Fractions >>
Related subject
Common keywords: APMO, Chinese, Iberoamerican, Polish.
user
The text passage contains a series of mathematical problems and their solutions from the 32nd USA Mathematical Olympiad 2003. Each problem is presented with a detailed solution.

TYPE: MULTIPLE_QUESTIONS_WITH_ANSWERS