18th Iberoamerican Mathematical Olympiad Problems 2003

A1.  Let A, B be two sets of N consecutive integers. If N = 2003, can we form N pairs (a, b) with a ∈ A, b ∈ B such that the sums of the pairs are N consecutive integers? What about N = 2004?

A2.  C is a point on the semicircle with diameter AB. D is a point on the arc BC. M, P, N are the midpoints of AC, CD and BD. The circumcenters of ACP and BDP are O, O'. Show that MN and OO' are parallel.

A3.  Pablo was trying to solve the following problem: find the sequence x₀, x₁, x₂, ... , x₂₀₀₃ which satisfies x₀ = 1, 0 ≤ x_i ≤ 2 x_i-1 for 1 ≤ i ≤ 2003 and which maximises S. Unfortunately he could not remember the expression for S, but he knew that it had the form S = ± x₁ ± x₂ ± ... ± x₂₀₀₂ + x₂₀₀₃. Show that he can still solve the problem.

B1.  A ⊆ {1, 2, 3, ... , 49} does not contain six consecutive integers. Find the largest possible value of |A|. How many such subsets are there (of the maximum size)?

B2.  ABCD is a square. P, Q are points on the sides BC, CD respectively, distinct from the endpoints such that BP = CQ. X, Y are points on AP, AQ respectively. Show that there is a triangle with side lengths BX, XY, YD.

B3.  The sequences a₀, a₁, a₂, ... and b₀, b₁, b₂, ... are defined by a₀ = 1, b₀ = 4, a_n+1 = a_n²⁰⁰¹ + b_n, b_n+1 = b_n²⁰⁰¹ + a_n. Show that no member of either sequence is divisible by 2003. 

Solutions

Problem A1

Let A, B be two sets of N consecutive integers. If N = 2003, can we form N pairs (a, b) with a ∈ A, b ∈ B such that the sums of the pairs are N consecutive integers? What about N = 2004?

Answer

Yes, no.

Solution

wlog A = B = {1, 2, ... , N} - if we have a solution for A = {a+1, a+2, ... , a+N} and B = {b+1, b+2, ... , b+N}, then subtracting a from every element of A and b from every element of b gives a solution for A = B = {1, 2, ... , N}. Suppose the sum set is (m+1), (m+2), ... , (m+N). It has sum N(2m+N+1)/2 and A and B each have sum N(N+1)/2, so we must have 2m = N+1, hence N must be odd. So we cannot do it for N = 2004.

Suppose N = 2M+1, take the pairs (1,M+1), (3,M), (5,M-1), ... , (2M+1,1), (2,2M+1), (4, 2M), ... , (2M, M+2). 

Problem A2

C is a point on the semicircle with diameter AB. D is a point on the arc BC. M, P, N are the midpoints of AC, CD and BD. The circumcenters of ACP and BDP are O, O'. Show that MN and OO' are parallel.

Solution

Let the center of the circle be X and the radius r. Let ∠AXM = θ, ∠BXN = φ. Note that O is the intersection of XM and the perpendicular to CD at Q, the midpoint of CP. We have XM = r cos θ. Let CD and XM meet at Y. Then ∠PYX = 90^o - ∠PXY = 90^o - ∠PXC - ∠CXM = θ + φ - φ = θ. Hence OX = PQ sec φ, so OX/XM = PQ/(r cos θ cos φ). Similarly, O'X/ON = PQ/(r cos θ cos φ), so OO' and MN are parallel. 

Problem A3

Pablo was trying to solve the following problem: find the sequence x₀, x₁, x₂, ... , x₂₀₀₃ which satisfies x₀ = 1, 0 ≤ x_i ≤ 2 x_i-1 for 1 ≤ i ≤ 2003 and which maximises S. Unfortunately he could not remember the expression for S, but he knew that it had the form S = ± x₁ ± x₂ ± ... ± x₂₀₀₂ + x₂₀₀₃. Show that he can still solve the problem.

Solution

For any combination of signs the maximum is obtained by taking all x_i as large as possible. Suppose we have a different set of x_i. Then for some k we must have x_k < 2x_k-1 and x_i = 2x_i-1 for all i > k. Suppose 2x^k-1 - x^k = h > 0. Then we can increase x_k by h, x_k+1 by 2h, x_k+2 by 4h, ... . So the sum will be increased by h(± 1 ± 2 ± ... ± 2^m-1 + 2^m) for some m ≥ 0. But ± 1 ± 2 ± ... ± 2^m-1 ≥ -(1 + 2 + ... + 2^m-1) = -2^m + 1, so the overall sum will be increased by at least 1. So the set of x_i was not maximal. 

Problem B1

A ⊆ {1, 2, 3, ... , 49} does not contain six consecutive integers. Find the largest possible value of |A|. How many such subsets are there (of the maximum size)?

Answer

max = 41; no. ways 495

Solution

We must exclude at least one element of each of the 8 sets {1, 2, ... , 6}, {7, ... , 12}, {13, ... , 18}, ... , {43, ... , 48}. So |A| ≤ 41. But a value of 41 is certainly possible, for example, exclude 2, 8, 14, ... , 44.

The largest excluded element must be at least 44 (or we have the 6 consecutive elements 44, 45, 46, 47, 48, 49). The smallest excluded element must be at most 6. If we exclude 2 and 44, then the difference between them is 7·6 and so the other 6 excluded elements are fixed. But if we exclude 3 and 44, for example, then there are several possible choices for the other elements.

There are 5 ways of choosing the smallest and largest excluded element to get a difference of 7·6 between them (2 and 44, 3 and 45, 4 and 46, 5 and 47, 6 and 48). There are 4 ways to get a difference of 7·6 - 1 (3 and 44, 4 and 45, 5 and 46, 6 and 47). There are 3 ways to get a difference of 7·6 - 2 (4 and 44, 5 and 45, 6 and 46), 2 ways to get a difference of 7·6 - 3 (5 and 44, 6 and 45), and 1 way to get a difference of 7·6 - 4 (6 and 44).

If the difference is 7·6 - 1, then we can shorten any of the 7 gaps, so there are 7 possibilities. For example, with 3 and 44, we could shorten the first gap, so excluding 3, 8, 14, 20, 26, 32, 38 and 44, or the second gap, so excluding 3, 9, 14, 20, 26, 32, 38 and 44, and so on.

If the difference is 7·6 - 2, then we can shorten one gap by two (7 possibilities) or two gaps by one (21 possibilities), total 28. If the difference is 7·6 - 3, then we can shorten on gap by three (7), one by two and one by one (42) or three by one (35), total 84. Finally, if the difference is 7·6 - 4, we can shorten one by four (7), one by three and one by 1 (42), two by two (21), one by two and two by one (105), or four by one (35), total 210.

So the total number of possibilities is 5·1 + 4·7 + 3·28 + 2·84 + 1·210 = 495. 

Problem B2

ABCD is a square. P, Q are points on the sides BC, CD respectively, distinct from the endpoints such that BP = CQ. X, Y are points on AP, AQ respectively. Show that there is a triangle with side lengths BX, XY, YD.

Solution

We have DY < BY ≤ BX + XY (this is almost obvious, but to prove formally use the cosine formula for BAY and DAY and notice that ∠BAY > ∠DAY). Similarly, BX < DX ≤ DY + YX. So it remains to show that XY < BX + DY.

Take Q' on the extension of BC so that BQ' = DQ, as shown in the diagram. Take Y' on AQ' so that AY' = AY. Then XY' ≤ BX + BY' = BX + DY. Now we claim that ∠PAQ' > ∠ PAQ, so it follows by the same observation as above that XY' > XY. But the claim is almost obvious. Note that PQ' = AB

So take P' on AD with ∠P'PQ' = 90^o. Then A lies inside the circle P'PQ', so extend PA to meet it again at A'. Then ∠PA'Q' = ∠PP'Q' = 45^o, so ∠PAQ' = ∠PA'Q' + ∠AQ'Q' > 45^o. But ∠PAQ' + ∠PAQ = 90^o, so ∠ PAQ' > ∠ PAQ as claimed. 

 Problem B3

The sequences a₀, a₁, a₂, ... and b₀, b₁, b₂, ... are defined by a₀ = 1, b₀ = 4, a_n+1 = a_n²⁰⁰¹ + b_n, b_n+1 = b_n²⁰⁰¹ + a_n. Show that no member of either sequence is divisible by 2003.

Solution

2003 is prime, so a²⁰⁰² = 1 mod 2003 for any a not divisible by 2003. Thus a_n+1 = a_n^-1 + b_n mod 2003, b_n+1 = b_n^-1 + a_n mod 2003. Put c_n = a_nb_n. Then c_n+1 = c_n + 1/c_n + 2 = (c_n + 1)₂/c_n mod 2003. So if c_n ≠ 0 mod 2003, then c_n+1 ≠ 0 mod 2003 unless c_n = -1 mod 2003. Then if c_n+1 = -1 mod 2003, we must have (c_n² + 3c_n + 1)/c_n = 0 mod 2003, so c_n² + 3c_n + 1 = 0 mod 2003. Note that c₀ = 4. So it is sufficient to show that there are no solutions to x² + 3x + 1 = 0 mod 2003, or equivalently to (x - 1000)² = 1000² - 1 = 502 mod 2003. In other words, we have to show that 502 is a quadratic non-residue mod 2003.

The easiest way to do that is to use the law of quadratic reciprocity, but that is almost certainly outside the syllabus. We note that 4·502 = 5 mod 2003, so 502 is a square iff 5 is a square. It is sufficient to show that 5¹⁰⁰¹ = -1 mod 2003, for then if we had x² = 5, we would have x²⁰⁰² = -1 mod 2003, whereas we know that x²⁰⁰² = 1 mod 2003. We note that 1001 = 7·11·13. We start by showing that 5⁷ = 8 mod 2003. We have 5⁵ = 3125 = 1122 mod 2003, so 5⁶ = 5610 = 1604 mod 2003, so 5⁷ = 8020 = 8 mod 2003.

We calculate successively 2¹¹ = 2048 = 45 mod 2003, so 2²² = 2025 = 22 mod 2003. Multiplying by 22 is relatively easy, so 2⁴⁴ = 484, 2⁶⁶ = 10648 = 633, 2⁸⁸ = 13926 = -95, 2¹¹⁰ = -2090 = -87, 2¹³² = -1914 = 89, 2¹⁴³ = 4005 = -1 all mod 2003. Hence 8^11·13 = -1 mod 2003, so 5¹⁰⁰¹ = -1 mod 2003, as required, and we are done.