14th Mexican Mathematical Olympiad Problems 2000

14th Mexican Mathematical Olympiad Problems 2000

A1.  A, B, C, D are circles such that A and B touch externally at P, B and C touch externally at Q, C and D touch externally at R, and D and A touch externally at S. A does not intersect C, and B does not intersect D. Show that PQRS is cyclic. If A and C have radius 2, B and D have radius 3, and the distance between the centers of A and C is 6, find area PQRS.

A2.  A triangle is constructed like that below, but with 1, 2, 3, ... , 2000 as the first row. Each number is the sum of the two numbers immediately above. Find the number at the bottom of the triangle.

1   2   3   4   5
  3   5   7   9
    8   12  16
      20  28
        48

A3.  If A is a set of positive integers, take the set A' to be all elements which can be written as ± a₁ ± a₂ ... ± a_n, where a_i are distinct elements of A. Similarly, form A" from A'. What is the smallest set A such that A" contains all of 1, 2, 3, ... , 40?

B1.  Given positive integers a, b (neither a multiple of 5) we construct a sequence as follows: a₁ = 5, a_n+1 = a a_n + b. What is the largest number of primes that can be obtained before the first composite member of the sequence?

B2.  Given an n x n board with squares colored alternately black and white like a chessboard. An allowed move is to take a rectangle of squares (with one side greater than one square, and both sides odd or both sides even) and change the color of each square in the rectangle. For which n is it possible to end up with all the squares the same color by a sequence of allowed moves?

B3.  ABC is a triangle with ∠B > 90^o. H is a point on the side AC such that AH = BH and BH is perpendicular to BC. D, E are the midpoints of AB, BC. The line through H parallel to AB meets DE at F. Show that ∠BCF = ∠ACD.

Solutions

Problem A2

A, B, C, D are circles such that A and B touch externally at P, B and C touch externally at Q, C and D touch externally at R, and D and A touch externally at S. A does not intersect C, and B does not intersect D. Show that PQRS is cyclic. If A and C have radius 2, B and D have radius 3, and the distance between the centers of A and C is 6, find area PQRS.

Answer
288/25
Solution

∠P = 180^o - a - b, ∠Q = 180^o - b - c, ∠R = 180^o - c - d, ∠S = 180^o - a - d. Hence ∠P + ∠R = ∠Q + ∠S. Hence ∠P + ∠R = 180^o, so PQRS is cyclic.

We have EG = 6, EF = FG = GH = HE = 5. EP = EQ = GR = GS = 2. Hence area EPQ = area GRS = (4/25) area EFH = (2/25) area EFGH. Similarly, area FQR = area HPS = (9/25) area FEG = (9/50) area EFGH. Hence area PQRS = (12/25) area EFGH = (24/25) area EFG. If M is the midpoint of EG, then EMF is a 3,4,5 triangle, so MF = 4 and area EFG = 12. So area PQRS = 288/25.

Problem A2

A triangle is constructed like that below, but with 1, 2, 3, ... , 2000 as the first row. Each number is the sum of the two numbers immediately above. Find the number at the bottom of the triangle.

1   2   3   4   5
  3   5   7   9
    8   12  16
      20  28
        48

Answer

2¹⁹⁹⁸2001

Solution

We claim that row n is 2^n-2(n+1), 2^n-2(n+1)+2^n-1, 2^n-2(n+1)+2·2^n-1, 2^n-2(n+1)+3·2^n-1, ... . It is obvious for n = 2. Suppose it is true for n. Then row n+1 is 2^n-1(n+2), 2^n-1(n+2)+2ⁿ, 2^n-1(n+2)+2·2ⁿ, 2^n-1(n+2)+3·2ⁿ, ... and so it is true for n+1 and hence for all n.

In particular, row 2000 has first term (and only term if the first row has only 2000 terms) 2¹⁹⁹⁸2001.

Thanks to Suat Namli

Problem A3

If A is a set of positive integers, take the set A' to be all elements which can be written as ± a₁ ± a₂ ... ± a_n, where a_i are distinct elements of A. Similarly, form A" from A'. What is the smallest set A such that A" contains all of 1, 2, 3, ... , 40?

Answer

3 elements, eg {1,5,25}

Solution

A = {1,5,25} works. We get A' = {1,4,5,6,19,20,21,24,25,26,29,30,31}. Then A" includes all n ≤ 40.

Suppose A = {a,b} works with a < b. Then A' = {a,b-a,b,b+a}. Now A" has at most 81 elements - for each element x ∈ A' we can include +x, -x or 0 in the sum, a total of 81 possibilities. However, this includes the empty sum 0. Also for every positive k ∈ A", -k is also included (reversing each sign in the sum). So at best A" can include 40 positive elements. But a and b - (b-a) are the same, so A" must include less than 40 positive elements.

Problem B1

Given positive integers a, b (neither a multiple of 5) we construct a sequence as follows: a₁ = 5, a_n+1 = a a_n + b. What is the largest number of primes that can be obtained before the first composite member of the sequence?

Answer

5

Solution

We find that the first few terms are a₁ = 5, a₂ = 5a+b, a₃ = 5a²+ab+b, a₄ = 5a³+a²b+ab+b, a₅ = 5a⁴+a³b+a²b+ab+b = 5a⁴ + b(a⁴-1)/(a-1), a₆ = 5a⁵+a⁴b+a³b+a²b+ab+b.

Now if a ≠ 1 mod 5, then a₄ = 1 mod 5, so a₅ = 0 mod 5. If a = 1 mod 5, then a₆ = b(a⁴+a³+a²+a+1) = b(1+1+1+1+1) = 0 mod 5. So either a₅ or a₆ is a multiple of 5 (and obviously greater than 5, so composite). Thus we can get at most 5 initial primes.

We find that for a = 6, b = 7 we get 5, 37, 229, 1381, 8293, which are all prime (although checking the last two is a considerable slog, we have to test 8293 for prime divisors up to 89).

Problem B2

Given an n x n board with squares colored alternately black and white like a chessboard. An allowed move is to take a rectangle of squares (with one side greater than one square, and both sides odd or both sides even) and change the color of each square in the rectangle. For which n is it possible to end up with all the squares the same color by a sequence of allowed moves?

Answer

n ≠ 2

Solution

For n odd we can invert a 1 x n rectangle, so we invert alternate columns. That gives the first row black, the second white, the third black and so on. So by inverting alternate rows we get all squares the same color.

Now if we can do n, then we can do 2n, because we can divide the 2n x 2n board into 4 equal parts and do each part separately. We can do n = 4 by four 3 x 1 moves and two 2 x 2 moves as follows:

B W B W  B W B B  B W B B  B B W W  B B W W  W W W W  W W W W
W B W B  W B W W  W B W W  W B W W  B B W W  W W W W  W W W W
B W B W  B W B B  B W B B  B W B B  W W B B  W W B B  W W W W
W B W B  W B W B  B W B B  B W B B  W W B B  W W B B  W W W W

Hence we can do all n ≥ 3. n = 2 is obviously impossible. n = 1 is trivially possible (do nothing).

Problem B3

ABC is a triangle with ∠B > 90^o. H is a point on the side AC such that AH = BH and BH is perpendicular to BC. D, E are the midpoints of AB, BC. The line through H parallel to AB meets DE at F. Show that ∠BCF = ∠ACD.

Solution

Put ∠A = α. AD is parallel to HF, and DF is parallel to AH, so DFHA is a parallelogram. Hence FH = AD = DB, so FH is equal and parallel to BD, so BFHD is a parallelogram. Hence ∠FBD = ∠BDH = 90^o (since HB = HA). Hence ∠FBC = ∠HBA = α.

BF = DH = AD tan α. We have ∠BHC = ∠HAB + ∠HBA = 2α, so BC/AC = BC/(AH+HC) = BC/(BH + HC) = HC sin 2α/(HC cos 2α + HC) = 2 sin α cos α/2 cos²α = tan α. So the triangles BFC and ADC are similar (∠FBC = ∠DAC and FB/BC = DA/AC). Hence ∠BCF = ∠ACD.