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.

[Read More...]

17th Iberoamerican Mathematical Olympiad Problems 2002

A1.  The numbers 1, 2, ... , 2002 are written in order on a blackboard. Then the 1st, 4th, 7th, ... , 3k+1th, ... numbers in the list are erased. Then the 1st, 4th, 7th, ... 3k+1th numbers in the remaining list are erased (leaving 3, 5, 8, 9, 12, ... ). This process is carried out repeatedly until there are no numbers left. What is the last number to be erased?

A2.  Given a set of 9 points in the plane, no three collinear, show that for each point P in the set, the number of triangles containing P formed from the other 8 points in the set must be even.

A3.  ABC is an equilateral triangle. P is a variable interior point such that angle APC = 120^o. The ray CP meets AB at M, and the ray AP meets BC at N. What is the locus of the circumcenter of the triangle MBN as P varies?

B1.  ABC is a triangle. BD is the an angle bisector. E, F are the feet of the perpendiculars from A, C respectively to the line BD. M is the foot of the perpendicular from D to the line BC. Show that ∠DME = ∠DMF.

B2.  The sequence a_n is defined as follows: a₁ = 56, a_n+1 = a_n - 1/a_n. Show that a_n < 0 for some n such that 0 < n < 2002.

B3.  A game is played on a 2001 x 2001 board as follows. The first player's piece is the policeman, the second player's piece is the robber. Each piece can move one square south, one square east or one square northwest. In addition, the policeman (but not the robber) can move from the bottom right to the top left square in a single move. The policeman starts in the central square, and the robber starts one square diagonally northeast of the policeman. If the policeman moves onto the same square as the robber, then the robber is captured and the first player wins. However, the robber may move onto the same square as the policeman without being captured (and play continues). Show that the robber can avoid capture for at least 10000 moves, but that the policeman can ultimately capture the robber. 

Solutions

Problem A1

The numbers 1, 2, ... , 2002 are written in order on a blackboard. Then the 1st, 4th, 7th, ... , 3k+1th, ... numbers in the list are erased. Then the 1st, 4th, 7th, ... 3k+1th numbers in the remaining list are erased (leaving 3, 5, 8, 9, 12, ... ). This process is carried out repeatedly until there are no numbers left. What is the last number to be erased?
Solution

Answer: 1598.
Let a_n be the first number remaining after n iterations, so a₀ = 1, a₁ = 2, a₃ = 3, a₄ = 5 etc. We claim that:

an+1 =  3/2  an   if an is even, and

 3/2 (an + 1) - 1 if an is odd.

We use induction on n. Suppose a_n = 2N. Consider the number 3N. There are initially N smaller numbers = 1 mod 3. So after the first iteration, it will lie in 2Nth place. Hence, it will lie in first place after n+1 iterations. Similarly, suppose a_n = 2N+1. Consider 3N+2. There are initially N+1 smaller numbers = 1 mod 3. So after the first iteration, it will lie in 2N+1st place. Hence, it will lie in first place after n+1 iterations. That completes the induction. We may now calculate successively the members of the sequence: 1, 2, 3, 5, 8, 12, 18, 27, 41, 62, 93, 140, 210, 315, 473, 710, 1065, 1598, 2397. Hence 1598 is the last surviving number from 1, 2, ... , 2002.

Problem A2

Given a set of 9 points in the plane, no three collinear, show that for each point P in the set, the number of triangles containing P formed from the other 8 points in the set must be even.
Solution

Join each pair of points, thus dividing the plane into polygonal regions. If a point P moves around within one of the regions then the number of triangles it belongs to does not change. But if it crosses one of the lines then it leaves some triangles and enters others. Suppose the line is part of the segment joining the points Q and R of the set. Then it can only enter or leave a triangle QRX for some X in the set. Suppose x points in the set lie on the same side of the line QR as P. Then there are 6 - x points on the other side of the line QR. So P leaves x triangles and enters 6-x. Thus the net change is even. Thus if we move P until it is in the outer infinite region (outside the convex hull of the other 8 points), then we change the number of triangles by an even number. But in the outside region it belongs to no triangles.
Note that the same argument works for any odd number of points.

Problem A3

ABC is an equilateral triangle. P is a variable interior point such that ∠APC = 120^o. The ray CP meets AB at M, and the ray AP meets BC at N. What is the locus of the circumcenter of the triangle MBN as P varies?
Solution

Answer: the segment of the perpendicular bisector of BG (where G is the center of the triangle) which forms a rectangle with AC.

∠MPN = ∠APC = 120^o and ∠MBN = 60^o, so MBNP is cyclic, in other words, P lies on the circumcircle of BMN.
P also lies on the circle AGC, so ∠CPG = ∠CAG (if P is on the same side of AG as A) = 30^o = ∠MBG. So PMBG is cyclic. In other words, G also lies on the circumcircle of BMN. If P lies on the other side, the same conclusion follows from considering ∠APG.
Since B and G lie on the circumcircle, the center O must lie on the perpendicular bisector of BG. But it is clear that the extreme positions of O occur when P is at A and B and that these are the feet of the perpendiculars from A and B to the perpendicular bisector.

Problem B1

ABC is a triangle. BD is the an angle bisector. E, F are the feet of the perpendiculars from A, C respectively to the line BD. M is the foot of the perpendicular from D to the line BC. Show that ∠DME = ∠DMF.
Solution


Let H be the foot of the perpendicular from D to AB. ∠AHD = ∠AED = 90^o, so AHED is cyclic. Hence ∠DAE = ∠DHE. But M is the reflection of H is the line BD, so ∠DME = ∠DAE.
AE is parallel to CD, so ∠DAE = ∠DCF. ∠DFC = ∠DMC, so DMCF is cyclic. Hence ∠DCF = ∠DMF. Hence ∠DME = ∠DMF.

Problem B2

The sequence a_n is defined as follows: a₁ = 56, a_n+1 = a_n - 1/a_n. Show that a_n < 0 for some n such that 0 < n < 2002.
Solution

Note that whilst a_n remains positive we have a₁ > a₂ > a₃ > ... > a_n. Hence if a_m and a_m+n are in this part of the sequence, then a_m+1 = a_m - 1/a_m, a_m+2 = a_m+1 - 1/a_m+1 < a_m+1 - 1/a_m = a_m - 2/a_m. By a trivial induction a_m+n < a_m - n/a_m.
If we use one step then we need 56² = 3136 terms to get a₁₊₃₁₃₆ < 56 - 56²/56 = 0, which is not good enough. So we try several steps.
Thus suppose that a_n > 0 for all n<= 2002. Then we get successively:
a₃₃₇ < 56 - 336/56 = 50
a₈₃₇ < 50 - 500/50 = 40
a₁₂₃₇ < 40 - 400/40 = 30
a₁₅₃₇ < 30 - 300/30 = 20
a₁₇₃₇ < 20 - 200/20 = 10
a₁₈₃₇ < 10 - 100/10 = 0.
Contradiction. So we must have a_n < 0 for some n < 2002.
Using Maple, we find that a_n is first negative for n = 1572. 

Problem B3

A game is played on a 2001 x 2001 board as follows. The first player's piece is the policeman, the second player's piece is the robber. Each piece can move one square south, one square east or one square northwest. In addition, the policeman (but not the robber) can move from the bottom right to the top left square in a single move. The policeman starts in the central square, and the robber starts one square diagonally northeast of the policeman. If the policeman moves onto the same square as the robber, then the robber is captured and the first player wins. However, the robber may move onto the same square as the policeman without being captured (and play continues). Show that the robber can avoid capture for at least 10000 moves, but that the policeman can ultimately capture the robber.
Solution

Color the squares with three colors as follows:

0  1  2  0  1  2  0  ...   2

1  2  0  1  2  0  1  ...   0

2  0  1  2  0  1  2  ...   1

0  1  2  0  1  2  0  ...   2

1  2  0  1  2  0  1  ...   0

...

2  0  1  2  0  1  2  ...   1

The middle square is color 2 (moving 999+1 squares E from the top left increases the color by 1, then moving 999+1 S increases it by another 1) and the square immediately NE of it is also 2. So both P and R start on color 2. Note that any move increases the color by 1 mod 3, except for P's special move which changes the color from 1 to 0. Until P has made this move, after each move of P, P's color is always 1 more than R's color (mod 3), so P cannot win (irrespective of the moves made by either player). Immediately after he makes the special move for the first time, P is on color 0 and R is on color 1, so immediately after his move P's color is now 1 less than R's color mod 3. Again P cannot win. But after P has made the special move for the second time, P's color is the same as R's (mod 3) immediately after P's move.
Note that it takes P at least 2001 moves to complete his special move for the first time and at least 6002 moves (in total) to complete his special move for the second time. This solves the first part of the question. Suppose R just moves down to the bottom right and then moves in small circles (one move NW, one move S, one move E) waiting for P. It takes P at least 6002 + 3999 (moving from top left to the capture square, one square short of the bottom right) = 10001 to capture him, so R makes at least 10000 moves before being captured.
We claim that P wins if he can get into any of the positions shown below relative to R, with R to move (*):

x  P  x  x  x

P  x  x  P  x

x  x  R  x  x

x  P  x  x  P

x  x  x  P  x

If follows that P can also win from the four positions below (**):

x  x  x  P  x  x  x

x  x  x  x  x  x  x

x  x  x  x  x  x  x

P  x  x  R  x  x  P

x  x  x  x  x  x  x

x  x  x  x  x  x  x

x  x  x  P  x  x  x

For in each case at least one of R's possible moves allow P to move immediately into one of the winning positions at (*). But R can only make the other moves a limited number of times before running into the border. [That is obvious if the other two moves are E and S. If they are NW and E, then every NW move takes R closer to the top border, but his total number of E moves can never exceed his total number of NW moves by more than 2000 because of the right border. Similarly, for NW and S.] Now let d be the number of rows plus the number of columns that R and P are apart. It is easy to check that the positions in (*) and (**) represent the only possibilities for d = 2 and 3. We show that P can always get to d = 2 or 3. For P can always copy R's move, so he can certainly move so that d never increases. But one of R's moves will always allow P to decrease d by 1 or 2. There are three cases to consider:
Case 1. If P is east of R and R moves E, then P moving NW will decrease d by 1 or 2. That is not possible if P is in the top row, but then moving S will decrease d by 2 unless R is also in the top row. If both are in the top row, then P moves S. Now after R's next move, P moves NW which reduces d by 2.
Case 2. If P is south of R and R moves S, then a similar argument, shows that P can always decrease d by 1 or 2 in one or two moves.
Case 3. If P is not south or east or R, and R moves NW, then P can always decrease d by 1 or 2 by moving S or E.
But repeated decreases by 1 or 2 must bring d ultimately to 2 or 3 and hence to one of (*) or (**). So P can always win.
It remains to prove the claim that (*) are winning positions. The reason is that in each case R has one move blocked off, so must make one of the other two. P then copies R's move, so next turn R has the same move blocked off. Repeated use of the other two moves will bring him ultimately to one of the sides.
We start with the easiest case: in the two following positions. R cannot move to z, so he must move east or south on each move. Hence he will (after at most 4000 moves) reach the bottom right corner. He then loses moving out of it.

x  P  x

P  z  x

x  x  R

The other cases of (*) are slightly more complicated. Starting from either of the two positions below, we show that R must eventually reach the extreme left column.

w  x  P  x

x  R  z  x

x  y  x  P

R cannot move to z, so he can only make NW and S moves. But his total number of S moves can never exceed his total number of NW moves by more than 2000 because he cannot move off the bottom of the board, so he must eventually reach the extreme left column. [If he reaches the bottom row at y, then P can always move to z to preserve the configuration. If R reaches the top row by moving to w, then P can always move to z to preserve the configuration.] Having reached the extreme left column he is forced to move south. Eventually moving to y will take him to the corner. P then moves to z and R is captured on his next move.
The final case to consider is the two positions below. R cannot move to z, so must move E or NW. A similar argument to the previous case shows that he must eventually reach the top row. Having reached it at w, P moves to z. So R is forced to move right along the top row. When he reaches the corner at y, P moves to z and R is captured when he moves out of the corner.

w  x  x

x  R  y

P  z  x

x  x  P

 

[Read More...]

16th Iberoamerican Mathematical Olympiad Problems 2001

A1.  Show that there are arbitrarily large numbers n such that: (1) all its digits are 2 or more; and (2) the product of any four of its digits divides n.

A2.  ABC is a triangle. The incircle has center I and touches the sides BC, CA, AB at D, E, F respectively. The rays BI and CI meet the line EF at P and Q respectively. Show that if DPQ is isosceles, then ABC is isosceles. 

A3.  Let X be a set with n elements. Given k > 2 subsets of X, each with at least r elements, show that we can always find two of them whose intersection has at least r - nk/(4k - 4) elements.

B1.  Call a set of 3 distinct elements which are in arithmetic progression a trio. What is the largest number of trios that can be subsets of a set of n distinct real numbers?

B2.  Two players play a game on a 2000 x 2001 board. Each has one piece and the players move their pieces alternately. A short move is one square in any direction (including diagonally) or no move at all. On his first turn each player makes a short move. On subsequent turns a player must make the same move as on his previous turn followed by a short move. This is treated as a single move. The board is assumed to wrap in both directions so a player on the edge of the board can move to the opposite edge. The first player wins if he can move his piece onto the same square as his opponent's piece. For example, suppose we label the squares from (0, 0) to (1999, 2000), and the first player's piece is initially at (0, 0) and the second player's at (1996, 3). The first player could move to (1999, 2000), then the second player to (1996, 2). Then the first player could move to (1998, 1998), then the second player to (1995, 1). Can the first player always win irrespective of the initial positions of the two pieces?

B3.  Show that a square with side 1 cannot be covered by five squares with side less than 1/2. 

Solutions

Problem A1

Show that there are arbitrarily large numbers n such that: (1) all its digits are 2 or more; and (2) the product of any four of its digits divides n.

Solution

3232 = 16 x 202 and 10000 = 16 x 625. So any number with 3232 as its last 4 digits is divisible by 16. So consider N = 22223232. Its sum of digits is 18, so it is divisible by 9. Hence it is divisible by 9.16 = 144. But any four digits have at most four 2s and at most two 3s, so the product of any four digits divides 144 and hence N. But now we can extend N by inserting an additional 9m 2s at the front. Its digit sum is increased by 18m, so it remains divisible by 144 and it is still divisible by the product of any four digits.

Alternative solution

The number 111111111 with nine 1s is divisible by 9. Hence the number with twenty-seven 1s which equals 111111111 x 1000000001000000001 is divisible by 27. So N, the number with twenty-seven 3s, is divisible by 3⁴. Now the number with 27n 3s is divisible by N and hence by 3⁴. 

Problem A2

ABC is a triangle. The incircle has center I and touches the sides BC, CA, AB at D, E, F respectively. The rays BI and CI meet the line EF at P and Q respectively. Show that if DPQ is isosceles, then ABC is isosceles.

Solution

AF = AE, so ∠AFE = 90^o - A/2. Hence ∠BFP = 90^o + A/2. But ∠FBP = B/2, so ∠FPB = C/2. But BFP and BDP are congruent (BF = BD, BP common, ∠FBP = ∠FDP), so ∠DPB = C/2 and ∠DPQ = C. Similarly, ∠DQP = B. Hence ∠PDQ = A. So DQP and ABC are similar. So if one is isosceles, so is the other.

Thanks to Johann Peter Gustav Lejeune Dirichlet

Problem B1

Call a set of 3 distinct elements which are in arithmetic progression a trio. What is the largest number of trios that can be subsets of a set of n distinct real numbers?

Answer

(m-1)m for n = 2m
m² for n = 2m+1

Solution

Let X be one of the elements. What is the largest number of trios that can have X as middle element? Obviously, at most max(b,a), where b is the number of elements smaller than X and a is the number larger. Thus if n = 2m, the no. of trios is at most 0 + 1 + 2 + ... + m-1 + m-1 + m-2 + ... + 1 + 0 = (m-1)m. If n = 2m+1, then the no. is at most 0 + 1 + 2 + ... + m-1 + m + m-1 + ... + 1 + 0 = m².

These maxima can be achieved by taking the numbers 1, 2, 3, ... , n.

[Read More...]

15th Iberoamerican Mathematical Olympiad Problems 2000

15th Iberoamerican Mathematical Olympiad Problems 2000

A1.  Label the vertices of a regular n-gon from 1 to n > 3. Draw all the diagonals. Show that if n is odd then we can label each side and diagonal with a number from 1 to n different from the labels of its endpoints so that at each vertex the sides and diagonals all have different labels.

A2.  Two circles C and C' have centers O and O' and meet at M and N. The common tangent closer to M touches C at A and C' at B. The line through B perpendicular to AM meets the line OO' at D. BO'B' is a diameter of C'. Show that M, D and B' are collinear. 

A3.  Find all solutions to (m + 1)^a = m^b + 1 in integers greater than 1.

B1.  Some terms are deleted from an infinite arithmetic progression 1, x, y, ... of real numbers to leave an infinite geometric progression 1, a, b, ... . Find all possible values of a.

B2.  Given a pile of 2000 stones, two players take turns in taking stones from the pile. Each player must remove 1, 2, 3, 4, or 5 stones from the pile at each turn, but may not take the same number as his opponent took on his last move. The player who takes the last stone wins. Does the first or second player have a winning strategy?

B3.  A convex hexagon is called a unit if it has four diagonals of length 1, whose endpoints include all the vertices of the hexagon. Show that there is a unit of area k for any 0 < k ≤ 1. What is the largest possible area for a unit? 

Solutions

Problem A1

Label the vertices of a regular n-gon from 1 to n > 3. Draw all the diagonals. Show that if n is odd then we can label each side and diagonal with a number from 1 to n different from the labels of its endpoints so that at each vertex the sides and diagonals all have different labels.
Solution

Labeling the diagonal/side between i and j as i+j (reduced if necessary mod n) almost works. The labels for all the lines at a given vertex will be different. But the line between i and n will have label i, the same as one endpoint. However, we are not using the label 2i for the lines from vertex i. So for the line between i and n we use 2i instead of i+n. The only points that need checking are (1) whether a line from i to n has a label different from n, and (2) whether all the lines at n have different labels. Both points are ok because n is odd.

Problem A2
Two circles C and C' have centers O and O' and meet at M and N. The common tangent closer to M touches C at A and C' at B. The line through B perpendicular to AM meets the line OO' at D. BO'B' is a diameter of C'. Show that M, D and B' are collinear.
Solution

A neat coordinate solution by Massaki Yamamoto (a competitor) is as follows.
Take AB as the x-axis and the perpendicular line through M as the y-axis. Choose the unit of length so that M has coordinates (0, 1). Let A be (-m, 0) and B be (n, 0). Then considering the right-angled triangle O'MK, where K is (n, 1) we find that O' is (n, (n²+1)/2 ). Similarly, O is (-m, (m²+1)/2 ) ).
The gradient of the lie AM is 1/m, so the gradient of the line BD is -m and hence its equation is mx + y = mn. The gradient of the line OO' is (n-m)/2, so its equation is 2y - x(n-m) = mn+1. These intersect at ( (mn-1)/(m+n), (mn²+m)/(m+n) ). B' is (n, n²+1). It is now easy to check that the lines MB' and MD both have gradient n, so M, D, B' are collinear.
This looks easy, but choosing the right coordinate system is critical. 

Problem A3
Find all solutions to (m + 1)^a = m^b + 1 in integers greater than 1.
Answer
(m, a, b) = (2, 2, 3).
Solution
Thanks to José Nelson Ramirez
Taking equation mod m+1 we get (-1)^b = -1, so b is odd. Hence we can divide the rhs by m+1 to get m^b-1 - m^b-2 + ... - m + 1. This has an odd number of terms. If m is odd, then each term is odd and so the total is odd, but (m+1)^a-1 is even (note that a > 1). Contradicton, so m is even.
We have m^b = (m+1)^a - 1. Expanding the rhs by the binomial theorem, and using b > 1, we see that m must divide a. So a is even also. Put a = 2A, m = 2M. We can factorise (m+1)^a - 1 as ( (m+1)^A + 1) ( (m+1)^A - 1). The two factors have difference 2, so their gcd divides 2, but both factors are even, so their gcd is exactly 2.
If M = 1 or a power of 2, then the smaller factor 3^A - 1 must be 2, so A = 1 and we have 3^A + 1 = 4, so (2M)^b = 8. Hence M = 1 and b = 3 and we have the solution (m, a, b) = (2, 2, 3).
If M is not a power of 2, then M^b > 2^b, so we must have the larger factor 2·M^b and the smaller factor 2^b-1. But the larger factor is now > 2^b+1, so the difference between the factors is at least 3·2^b-1 > 2. Contradiction.

Problem B1

Some terms are deleted from an infinite arithmetic progression 1, x, y, ... of real numbers to leave an infinite geometric progression 1, a, b, ... . Find all possible values of a.
Solution

Answer: the positive integers.
If a is negative, then the terms in the GP are alternately positive and negative, whereas either all terms in the AP from a certain point on are positive or all terms from a certain point on are negative. So a cannot be negative. If a is zero, then all terms in the GP except the first are zero, but at most one term of the AP is zero, so a cannot be zero. Thus a must be positive, so the AP must have infinitely many positive terms and hence x ≥ 1.
Let d = x - 1, so all terms of the AP have the form 1+nd for some positive integer n. Suppose a = 1 + md, a² = 1 + nd, then (1 + md)² = 1 + nd, so d = (n - 2m)/m², which is rational. Hence a is rational. Suppose a = b/c, where b and c are relatively prime positive integers and c > 1. Then the denominator of the nth term of the GP is cⁿ, which becomes arbitrarily large as n increases. But if d = h/k, then all terms of the AP have denominator at most k. So we cannot have c > 1. So a must be a positive integer.
On the other hand, it is easy to see that any positive integer works. Take x = 2, then the AP includes all positive integers and hence includes any GP with positive integer terms.

Problem B2

Given a pile of 2000 stones, two players take turns in taking stones from the pile. Each player must remove 1, 2, 3, 4, or 5 stones from the pile at each turn, but may not take the same number as his opponent took on his last move. The player who takes the last stone wins. Does the first or second player have a winning strategy?
Solution

The first player has a winning strategy. He takes 4 on his first move leaving 7 mod 13 (2000 = 153.13 + 7 + 4). Now we claim that the first player can always leave: (1) 0 mod 13, (2) 3 mod 13 by taking away 3, (3) 5 mod 13 by taking away 5, or (4) 7 mod 13, and that the second player can never leave 0 mod 13.
Let us look at each of these in turn. If the first player leaves 0 mod 13, then the second player can take 3 and leave 10. In that case the first player takes 5 (a type (3) move). If the second player takes 1, 2, 4 or 5, leaving 12, 11, 9 or 8 mod 13, then the first player takes 5, 4, 2, 1 (respectively) and leaves 7 mod 13 (a type (4) move).
If the first player leaves 3 mod 13 by taking away 3, then the second player cannot leave 0 mod 13, because he cannot take 3 stones. If he takes 1, 2 leaving 2, 1 mod 13 respectively, then the first player takes 2, 1 leaving 0 mod 13 (a type (1) move). If the second player takes 4, 5 leaving 12, 11 mod 13, then the first player takes 5, 4 leaving 7 mod 13 (a type (4) move).
If the first player leaves 5 mod 13 by taking 5, then the second player cannot leave 0 mod 13, because he cannot take 5 stones. If he takes 1, 2, 3, 4 stones, leaving 4, 3, 2, 1 mod 13, then the first player takes 4, 3, 2, 1 stones leaving 0 mod 13 (a type (1) move).
Finally, if the first player leaves 7 mod 13, and the second player takes 1 stone, then the first player takes 3 stones leaving 3 mod 13 (a type (2) move). If the second player takes 2, 3, 4, or 5 stones leaving 5, 4, 3, 2 mod 13, then the first player takes 5, 4, 3, 2 stones leaving 0 mod 13 (a type (1) move).
So the second player can never leave 0 mod 13 and hence, in particular, can never take the last stone. But we have shown that the first player can always make a move of one of the four types, so can always move and hence must win (since after less than 2000 moves there will be no stones left).

Problem B3
A convex hexagon is called a unit if it has four diagonals of length 1, whose endpoints include all the vertices of the hexagon. Show that there is a unit of area k for any 0 < k ≤ 1. What is the largest possible area for a unit?
Solution
Answer: We can get arbitrarily close to (but not achieve) (3√3)/4 (approx 1.3) by:

To prove the first part, consider the diagram below. Take AB = AC = 1 and angle BAC = 2θ. Take DE = DF = 1 and take the points of intersection X and Y such that AX = DX = AY = DY = 2/3. It is easy to check that the area of the hexagon is sin 2θ. So by taking θ in the interval (0, π/4] we can get any area 0 < k ≤ 1.

It is easy to check that there are six possible configurations for the unit diagonals, as shown in the diagram below.

Consider case 1.

 


The area of the hexagon is area AEDC + area AFE + area BAC. The part of the segment BF that lies inside AEDC is wasted. The rest goes to provide height for the triangles on bases AE and AC. So area AFE + area BAC can be maximised by taking F close to A and ∠BAC as close to a right angle as possible, so that the height of the triangle BAC (on the base AC) is as large as possible. We can then get arbitrarily close to the area of:

We obviously make AEB a straight line. Now area ADE + area ADC = area ACE + area CDE. So if we regard every point except D as fixed, then we maximise the area by taking ∠EAD = ∠CAD, so that D is the maximum distance from CE. Thus a maximal configuration must have ∠AED = ∠CAD. Similarly, it must have ∠CAD = ∠CAB, so all three angles must be equal. That disposes of case 1.
In cases 2 and 6 we find by a similar (but more tedious argument) the same maximum, although in one case we have to use the argument at the end for the final optimisation. In the other cases the maximum is smaller.

However, all these details would take an already long solution way over length. Does anyone have a better approach?
No. 6 (second case) can be made arbitrarily close to the figure below (with AB = AC = BD = 1). To optimise it, suppose ∠ACB = θ. Area ABDC = area ABC + area BCD. If we fix θ, then BC is fixed, so to maximise area BCD we must take ∠CBD = 90^o. But θ cannot be optimal unless also ∠CAD = 90^o. We have BA = BD and hence ∠BAD = ∠BDA = 45^o - θ/2. Hence 90^o = ∠CAD = ∠BAC - ∠BAD = (180^o - 2θ) - (45^o - θ/2). Hence θ = 30^o. So ∠ACD = ∠BDC = 60^o and ∠CAB = ∠ABD = 120^o. It is easy to check that this has area (3√3)/4.





 

[Read More...]

14th Iberoamerican Mathematical Olympiad Problems 1999

A1.  Find all positive integers n < 1000 such that the cube of the sum of the digits of n equals n².

A2.  Given two circles C and C' we say that C bisects C' if their common chord is a diameter of C'. Show that for any two circles which are not concentric, there are infinitely many circles which bisect them both. Find the locus of the centers of the bisecting circles.

A3.  Given points P₁, P₂, ... , P_n on a line we construct a circle on diameter P_iP_j for each pair i, j and we color the circle with one of k colors. For each k, find all n for which we can always find two circles of the same color with a common external tangent.

B1.  Show that any integer greater than 10 whose digits are all members of {1, 3, 7, 9} has a prime factor ≥ 11.

B2.  O is the circumcenter of the acute-angled triangle ABC. The altitudes are AD, BE and CF. The line EF cuts the circumcircle at P and Q. Show that OA is perpendicular to PQ. If M is the midpoint of BC, show that AP² = 2 AD·OM.

B3.  Given two points A and B, take C on the perpendicular bisector of AB. Define the sequence C₁, C₂, C₃, ... as follows. C₁ = C. If C_n is not on AB, then C_n+1 is the circumcenter of the triangle ABC_n. If C_n lies on AB, then C_n+1 is not defined and the sequence terminates. Find all points C such that the sequence is periodic from some point on.

[Read More...]

13th Iberoamerican Mathematical Olympiad Problems 1998

A1.  There are 98 points on a circle. Two players play alternately as follows. Each player joins two points which are not already joined. The game ends when every point has been joined to at least one other. The winner is the last player to play. Does the first or second player have a winning strategy?

A2.  The incircle of the triangle ABC touches BC, CA, AB at D, E, F respectively. AD meets the circle again at Q. Show that the line EQ passes through the midpoint of AF iff AC = BC.

A3.  Find the smallest number n such that given any n distinct numbers from {1, 2, 3, ... , 999}, one can choose four different numbers a, b, c, d such that a + 2b + 3c = d.

B1.  Representatives from n > 1 different countries sit around a table. If two people are from the same country then their respective right hand neighbors are from different countries. Find the maximum number of people who can sit at the table for each n.

B2.  P₁, P₂, ... , P_n are points in the plane and r₁, r₂, ... , r_n are real numbers such that the distance between P_i and P_j is r_i + r_j (for i not equal to j). Find the largest n for which this is possible.

B3.  k is the positive root of the equation x² - 1998x - 1 = 0. Define the sequence x₀, x₁, x₂, ... by x₀ = 1, x_n+1 = [k x_n]. Find the remainder when x₁₉₉₈ is divided by 1998.

[Read More...]

12th Iberoamerican Mathematical Olympiad Problems 1997

A1.  k ≥ 1 is a real number such that if m is a multiple of n, then [mk] is a multiple of [nk]. Show that k is an integer.

A2.  I is the incenter of the triangle ABC. A circle with center I meets the side BC at D and P, with D nearer to B. Similarly, it meets the side CA at E and Q, with E nearer to C, and it meets AB at F and R, with F nearer to A. The lines EF and QR meet at S, the lines FD and RP meet at T, and the lines DE and PQ meet at U. Show that the circumcircles of DUP, ESQ and FTR have a single point in common.

A3.  n > 1 is an integer. D_n is the set of lattice points (x, y) with |x|, |y| ≤ n. If the points of D_n are colored with three colors (one for each point), show that there are always two points with the same color such that the line containing them does not contain any other points of D_n. Show that it is possible to color the points of D_n with four colors (one for each point) so that if any line contains just two points of D_n then those two points have different colors.

B1.  Let o(n) be the number of 2n-tuples (a₁, a₂, ... , a_n, b₁, b₂, ... , b_n) such that each a_i, b_j = 0 or 1 and a₁b₁ + a₂b₂ + ... + a_nb_n is odd. Similarly, let e(n) be the number for which the sum is even. Show that o(n)/e(n) = (2ⁿ - 1)/(2ⁿ + 1).

B2.  ABC is an acute-angled triangle with orthocenter H. AE and BF are altitudes. AE is reflected in the angle bisector of angle A and BF is reflected in the angle bisector of angle B. The two reflections intersect at O. The rays AE and AO meet the circumcircle of ABC at M and N respectively. P is the intersection of BC and HN, R is the intersection of BC and OM, and S is the intersection of HR and OP. Show that AHSO is a parallelogram.

B3.  Given 1997 points inside a circle of radius 1, one of them the center of the circle. For each point take the distance to the closest (distinct) point. Show that the sum of the squares of the resulting distances is at most 9.

[Read More...]

11th Iberoamerican Mathematical Olympiad Problems 1996

A1.  Find the smallest positive integer n so that a cube with side n can be divided into 1996 cubes each with side a positive integer.

A2.  M is the midpoint of the median AD of the triangle ABC. The ray BM meets AC at N. Show that AB is tangent to the circumcircle of NBC iff BM/MN = (BC/BN)².

A3.  n = k² - k + 1, where k is a prime plus one. Show that we can color some squares of an n x n board black so that each row and column has exactly k black squares, but there is no rectangle with sides parallel to the sides of the board which has its four corner squares black.

B1.  n > 2 is an integer. Consider the pairs (a, b) of relatively prime positive integers, such that a < b ≤ n and a + b > n. Show that the sum of 1/ab taken over all such pairs is 1/2.

B2.  An equilateral triangle of side n is divided into n² equilateral triangles of side 1 by lines parallel to the sides. Initially, all the sides of all the small triangles are painted blue. Three coins A, B, C are placed at vertices of the small triangles. Each coin in turn is moved a distance 1 along a blue side to an adjacent vertex. The side it moves along is painted red, so once a coin has moved along a side, the side cannot be used again. More than one coin is allowed to occupy the same vertex. The coins are moved repeatedly in the order A, B, C, A, B, C, ... . Show that it is possible to paint all the sides red in this way.

B3.  A₁, A₂, ... , A_n are points in the plane. A non-zero real number k_i is assigned to each point, so that the square of the distance between A_i and A_j (for i ≠ j) is k_i + k_j. Show that n is at most 4 and that if n = 4, then 1/k₁ + 1/k₂ + 1/k₃ + 1/k₄ = 0.

Solutions

Problem A1

Find the smallest positive integer n so that a cube with side n can be divided into 1996 cubes each with side a positive integer.

Solution

Answer: 13.

Divide all the cubes into unit cubes. Then the 1996 cubes must each contain at least one unit cube, so the large cube contains at least 1996 unit cubes. But 12³ = 1728 < 1996 < 2197 = 13³, so it is certainly not possible for n < 13.

It can be achieved with 13 by 1.5³ + 11.2³ + 1984.1³ = 13³ (actually packing the cubes together to form a 13 x 13 x 13 cube is trivial since there are so many unit cubes).

Problem 2

M is the midpoint of the median AD of the triangle ABC. The ray BM meets AC at N. Show that AB is tangent to the circumcircle of NBC iff BM/BN = (BC/BN)².

Solution

Applying Menelaus to the triangle ADC, we have (AM/MD)(BD/DC)(CN/NA) = 1, so (CN/NA) = 2. Hence AN/AC = 1/3. Applying Menelaus to the triangle BNC, we have (BM/MN)(AN/AC)(CD/DB) = 1, so BM/MN = 3. That is true irrespective of whether AB is tangent to the circle NBC.

If AB is tangent, then AB² = AN.AC = 1/3 AC². Also angle ABN = angle BCN, so triangles ANB and ABC are similar. Hence BC/BN = AC/AB. Hence (BC/BN)² = 3 = BM/BN.

Conversely, if (BC/BN)² = BM/BN, then (BC/BN)² = 3.

Now applying the cosine formula to AMN and AMB and using cos AMN + cos AMB = 0, we have (3AN² - 3AM² - 3MN²) + (AB² - AM² - BM²) = 0, so AB² + AC²/3 = AD² + 3/4 BN². Similarly from triangles ADC and ADB we get AB² + AC² = 2AD² + BC²/2. So using BN² = BC²/3 we get 2AB² + 2/3 AC² = AB² + AC² and hence (AC/AB)² = 3 = (BC/BN)². So AC/AB = BC/BN. Note that is not enough to conclude that triangles ABC and BNC are similar, because the common angle C is not between AC and AB. However, we have AN/AB = (1/3) AC/AB = AB/AC, so AB² = AN.AC, so AB is tangent to the circle NBC.

Problem A3

n = k² - k + 1, where k is a prime plus one. Show that we can color some squares of an n x n board black so that each row and column has exactly k black squares, but there is no rectangle with sides parallel to the sides of the board which has its four corner squares black.

Solution

We can regard the rows as lines and the columns as points. Black squares denote incidence. So line 3 contains point 4 iff square (3, 4) is black. The condition about rectangles then means that there is at most one line through two distinct points.

Suppose we take the points to be (a, b, c), where a, b, c are residues mod p, not all zero, and the coordinates are homogeneous, so that we regard (a, b, c), (2a, 2b, 2c), ... , ( (p-1)a, (p-1)b, (p-1)c ) as the same point. That gives (p³ - 1)/(p-1) = p² + p + 1 points, which is the correct number.

We can take lines to be lx + my + nz = 0, where the point is (x, y, z). In other words, the lines are also triples (l, m, n), with l, m, n residues mod p, not all zero and (l, m, n), (2l, 2m, 2n), ... , ( (p-1)l, (p-1)m, (p-1)n ) representing the same line.

One way of writing the points is p² of the form (a, b, 1), p of the form (a, 1, 0) and lastly (1, 0, 0). Similarly for the lines. We must show that (1) each point is on p+1 lines (so each column has p+1 black squares), (2) each line has p+1 points (so each row has p+1 black squares, (3) two lines meet in just one point (so no rectangles).

(1): Consider the point P (a, b, 1) with a non-zero. Then for any m, there is a unique l such that la + mb + 1.1 = 0, so there are p lines of the form (l, m, 1) which contain P. Similarly, there is a unique l such that la + 1b + 0.1 = 0, so one line of the form (l, 1, 0) contains P. The line (1, 0, 0) does not contain P. So P lies on just p+1 lines. Similarly for (a, b, 1) with b non-zero. The point (0, 0, 1) does not lie on any lines (l, m,, 1), but lies on (l, 1, 0) and (1, 0, 0), so again it lies on p+1 lines.

Consider the point Q (a, 1, 0) with a non-zero. For any m, there is a unique l such that Q lies on (l, m, 0). There is also a unique l such that Q lies on (l, 1, 0). Q does not lie on (1, 0, 0), so it lies on just p+1 lines. Similarly, the point (0, 1, 0) lies on the p lines (l, 0, 0) and on (1, 0, 0), but no others.

Finally, the point (1, 0, 0) lies on the p lines (0, m, 1), the line (0, 1, 0) and no others. Thus in all cases a point lies on just p+1 lines. The proof of (2) is identical.

(3). Suppose the lines are (l, m, n) and (L, M, N). If l and L are non-zero, then we can take the lines as (1, m', n') and (1, M', N'). So any point (x, y, z) on both satisfies x + m'y + n'z = 0 (*) and x + M'y + N'z = 0. Subtracting, (m' - M')y + (n' - N')z = 0. The coefficients cannot both be zero, since the lines are distinct. So the ratio y : z is fixed. Then (*) gives the ratio x : y. So the point is uniquely determined. If just one of l, L is non-zero, then we can take the lines as (0, m', n'), (1, M', N'). We cannot have both m' and n' zero, so the ratio y : z is determined, then the other line determines the ratio x : y. So again the point is uniquely determined. Finally, suppose l and L are both zero. Then since the lines are distinct y and z must both be zero. So the unique point on both lines is (1, 0, 0).

Comment. This is a poor question. If you have not met finite projective geometries before, then you are in real difficulties. If you have, the proof is just tiresome verification.

Problem B1

n > 2 is an integer. Consider the pairs (a, b) of relatively prime positive integers, such that a < b ≤ n and a + b > n. Show that the sum of 1/ab taken over all such pairs is 1/2.

Solution

Induction on n. It is obvious for n = 3, because the only pairs are (1, 3) and (2, 3), and 1/3 + 1/6 = 1/2. Now suppose it is true for n. As we move to n+1, we introduce the new pairs (a, n+1) with a relatively prime to n+1 and we lose the pairs (a, n+1-a) with a relatively prime to n+1-a and hence to n+1. So for each a relatively prime to n+1 and < (n+1)/2 we gain (a, n+1) and (n+1-a, n+1) and lose (a, n+1-a). But 1/a(n+1) + 1/( (n+1-a)(n+1) ) = ( n+1-a + a)/( a(n+1-a)(n+1) ) = 1/( a(n+1-a) ).

Problem B2

An equilateral triangle of side n is divided into n² equilateral triangles of side 1 by lines parallel to the sides. Initially, all the sides of all the small triangles are painted blue. Three coins A, B, C are placed at vertices of the small triangles. Each coin in turn is moved a distance 1 along a blue side to an adjacent vertex. The side it moves along is painted red, so once a coin has moved along a side, the side cannot be used again. More than one coin is allowed to occupy the same vertex. The coins are moved repeatedly in the order A, B, C, A, B, C, ... . Show that it is possible to paint all the sides red in this way.

Solution

We use induction. It is obvious for n = 1 and 2 - see diagram above. Note that A, B, C start and end at vertices of the large triangle.

Now assume that for n we can find a solution with A, B, C starting and ending at the vertices of the large triangle. Take n+1. We start with the paths shown which bring A, B, C to A', B', C' at the vertices of a triangle side n-1. Now by induction we can continue the paths so that we bring A, B, C, back to the vertices of that triangle after tracing out all its edges. Finally, note that for each of the points A', B', C' there is a path length 2 over untraced segments to a vertex of the large triangle. So we get a solution for n+1 and hence for all n.

Problem B3

A₁, A₂, ... , A_n are points in the plane. A non-zero real number k_i is assigned to each point, so that the square of the distance between A_i and A_j (for i ≠ j) is k_i + k_j. Show that n is at most 4 and that if n = 4, then 1/k₁ + 1/k₂ + 1/k₃ + 1/k₄ = 0.

Solution

Suppose we have four points A, B, C, D with associated numbers a, b, c, d. Then AB² = a + b, AC² = a + c, so AB² - AC² = b - c. Similarly, DB² - DC² = b - c, so AB² - AC² = DB² - DC². Let X be the foot of the perpendicular from A to BC, and Y the foot of the perpendicular from D to BC. Then AB² - AC² = (AX² + XB²) - (AX² + XC²) = XB² - XC². Similarly for D, so XB² - XC² = YB² - YC². Hence X = Y, so AD is perpendicular to BC. Similarly, BD is perpendicular to AC, and CD is perpendicular to AB. Hence D is the (unique) orthocenter of ABC. So n <= 4.

Suppose n = 4, so we have four points A, B, C, D with associated numbers a, b, c, d. We have AB² + AC² - BC² = (a + b) + (a + c) - (b + c) = 2a. But by the cosine formula it is also 2 AB AC cos BAC. Hence a = AB AC cos BAC. Similarly for A, B, D etc. Hence ab/cd = (AB AC cos BAC)(BA BD cos ABD)/( (CA.CD cos ACD)(DB DC cos BDC) ) = (AB²/CD²) (cos BAC/cos BDC) (cos ABD/cos ACD).

Take ABC to be acute with D inside. Then angle ABD = angle ACD ( = 90^o - angle BAC), and angle BDC = 90^o + angle ACD = 180^o - angle BAC. So cos BAC/cos BDC = -1. Thus ab/cd = - AB²/CD² = - (a + b)/(c + d). Hence ab(c + d) + cd(a + b) = 0, so 1/a + 1/b + 1/c + 1/d = 0.

[Read More...]

10th Iberoamerican Mathematical Olympiad Problems 1995

A1.  Find all possible values for the sum of the digits of a square.

A2.  n > 1. Find all solutions in real numbers x₁, x₂, ... , x_n+1 all at least 1 such that: (1) x₁^1/2 + x₂^1/3 + x₃^1/4 + ... + x_n^1/(n+1) = n x_n+1^1/2; and (2) (x₁ + x₂ + ... + x_n)/n = x_n+1.

A3.  L and L' are two perpendicular lines not in the same plane. AA' is perpendicular to both lines, where A belongs to L and A' belongs to L'. S is the sphere with diameter AA'. For which points P on S can we find points X on L and X' on L' such that XX' touches S at P?

B1.  ABCD is an n x n board. We call a diagonal row of cells a positive diagonal if it is parallel to AC. How many coins must be placed on an n x n board such that every cell either has a coin or is in the same row, column or positive diagonal as a coin?

B2.  The incircle of the triangle ABC touches the sides BC, CA, AB at D, E, F respectively. AD meets the circle again at X and AX = XD. BX meets the circle again at Y and CX meets the circle again at Z. Show that EY = FZ.

B3.  f is a function defined on the positive integers with positive integer values. Use f ^m(n) to mean f(f( ... f(n) ....)) = n where f is taken m times, so that f ²(n) = f(f(n)), for example. Find the largest possible 0 < k < 1 such that for some function f, we have f ^m(n) ≠ n for m = 1, 2, ... , [kn], but f ^m(n) = n for some m (which may depend on n). 

Solutions

Problem A1

Find all possible values for the sum of the digits of a square.

Solution

Answer: any non-negative integer = 0, 1, 4 or 7 mod 9.

0² = 0, (±1)² = 1, (±2)² = 4, (±3)² = 0, (±4)² = 7 mod 9, so the condition is necessary.

We exhibit squares which give these values.

0 mod 9. Obviously 0² = 0. We have 9² = 81, 99² = 9801 and in general 9...9² = (10ⁿ - 1)² = 10²ⁿ - 2.10ⁿ + 1 = 9...980...01, with digit sum 9n.

1 mod 9. Obviously 1² = 1 with digit sum 1, and 8² = 64 with digit sum 10. We also have 98² = 9604, 998² = 996004, and in general 9...98² = (10ⁿ - 2)² = 10²ⁿ - 4.10ⁿ + 4 = 9...960...04, with digit sum 9n+1.

4 mod 9 Obviously 2² = 4 with digit sum 4, and 7² = 49 with digit sum 13. Also 97² = 9409 with digit sum 22, 997² = 994009 with digit sum 31, and in general 9...97² = (10ⁿ - 3)² = 10²ⁿ - 6.10ⁿ + 9 = 9...940...09, with digit sum 9n+4.

7 mod 9 Obviously 4² = 16, with digit sum 7. Also 95² = 9025, digit sum 16, 995² = 990025 with digit sum 25, and in general 9...95² = (10ⁿ - 5)² = 10²ⁿ - 10ⁿ⁺¹ + 25 = 9...90...025, with digit sum 9n-2. 

Problem A2

Find all solutions in real numbers x₁, x₂, ... , x_n+1 all at least 1 such that: (1) x₁^1/2 + x₂^1/3 + x₃^1/4 + ... + x_n^1/(n+1) = n x_n+1^1/2; and (2) (x₁ + x₂ + ... + x_n)/n = x_n+1.

Answer

The only solution is the obvious, all x_i = 1.

Solution

By Cauchy-Schwartz, (∑ x_i^1/2)² ≤ (∑ 1)(&sum x_i), with equality iff all x_i equal. In other words, if we put x_n+1 = (x₁ + x₂ + ... + x_n)/n, then ∑ x_i^1/2 ≤ n x_n+1^1/2. But since all x_i ≥ 1, we have x₁^1/2 + x₂^1/3 + x₃^1/4 + ... + x_n^1/(n+1) ≤ ∑ x_i^1/2 with equality iff x₂ = x₃ = ... = x_n = 1. Hence x₁^1/2 + x₂^1/3 + x₃^1/4 + ... + x_n^1/(n+1) ≤ x_n+1^1/2 with equality iff all x_i = 1. 

Problem B1

ABCD is an n x n board. We call a diagonal row of cells a positive diagonal if it is parallel to AC. How many coins must be placed on an n x n board such that every cell either has a coin or is in the same row, column or positive diagonal as a coin?

Answer

smallest integer ≥ (2n-1)/3
[so 2m-1 for n = 3m-1, 2m for n = 3m, 2m+1 for n = 3m+1]

Solution

There must be at least n-k rows without a coin and at least n-k columns without a coin. Let r₁, r₂, ... , r_n-k be cells in the top row without a coin which are also in a column without a coin. Let r₁, c₂, c₃, ... , c_n-k be cells in the first column without a coin which are also in a row without a coin. Each of the 2n-2k-1 r_i and c_j are on a different positive diagonal, so we must have k ≥ 2n-2k-1 and hence k ≥ (2n-1)/3.

Let (i,j) denote the cell in row i, col j. For n = 3m-1, put coins in (m,1), (m-1,2), (m-2,3), ... , (1,m) and in (2m-1,m+1), (2m-2,m+2), ... , (m+1,2m-1). It is easy to check that this works. For n = 3m, put an additional coin in (2m,2m), it is easy to check that works. For n = 3m+1 we can use the same arrangement as for 3m+2.

Problem B3

f is a function defined on the positive integers with positive integer values. Use f ^m(n) to mean f(f( ... f(n) ....)) = n where f is taken m times, so that f ²(n) = f(f(n)), for example. Find the largest possible 0 < k < 1 such that for some function f, we have f ^m(n) ≠ n for m = 1, 2, ... , [kn], but f ^m(n) = n for some m (which may depend on n).

Answer

we can get k arbitrarily close to 1

Solution

The basic idea is to take a block of integers m+1, m+2, ... , M and to define f(m+1) = m+2, f(m+2) = m+3, ... , f(M-1) = M, f(M) = m+1. Then for any integer h in the block we have fⁿ(h) ≠ h for n = 1, 2, ... , M-m-1 and f^M-m(h) = h. Note that the ratio (M-m)/h is worst (smallest) for h = M.

For example, take the first block to be 1, 2, ... , N, the second block to be N+1, ... , N², the third block, N²+1, ... , N³ and so on. Then for any integer n we have f^m(n) ≠ n for m < kn where k = 1 - 1/N.

[Read More...]

9th Iberoamerican Mathematical Olympiad Problems 1994

A1.  Show that there is a number 1 < b < 1993 such that if 1994 is written in base b then all its digits are the same. Show that there is no number 1 < b < 1992 such that if 1993 is written in base b then all its digits are the same.

A2.  ABCD is a cyclic quadrilateral. A circle whose center is on the side AB touches the other three sides. Show that AB = AD + BC. What is the maximum possible area of ABCD in terms of |AB| and |CD|?

A3.  There is a bulb in each cell of an n x n board. Initially all the bulbs are off. If a bulb is touched, that bulb and all the bulbs in the same row and column change state (those that are on, turn off, and those that are off, turn on). Show that it is possible by touching m bulbs to turn all the bulbs on. What is the minimum possible value of m?

B1.  ABC is an acute-angled triangle. P is a point inside its circumcircle. The rays AP, BP, CP intersect the circle again at D, E, F. Find P so that DEF is equilateral.

B2.  n and r are positive integers. Find the smallest k for which we can construct r subsets A₁, A₂, ... , A_r of {0, 1, 2, ... , n-1} each with k elements such that each integer 0 ≤ m < n can be written as a sum of one element from each of the r subsets.

B3.  Show that given any integer 0 < n ≤ 2^1000000 we can find at set S of at most 1100000 positive integers such that S includes 1 and n and every element of S except 1 is a sum of two (possibly equal) smaller elements of S. 

Solutions

Problem A1

Show that there is a number 1 < b < 1993 such that if 1994 is written in base b then all its digits are the same. Show that there is no number 1 < b < 1992 such that if 1993 is written in base b then all its digits are the same.

Solution

Any even number 2n can be written as 22 in base n-1. In particular 1994 = 22₉₉₆.

We have to show that we cannot write 1993 = aaa ... a_b. If the number has n digits, then 1993 = a(1 + b + ... + b^n-1) = a(bⁿ - 1)/(b - 1). But 1993 is prime, so a must be 1. Hence b^n-1 + ... + b - 1992 = 0. So b must divide 1992 = 2³3.83. We cannot have n = 2, for then b = 1992 and we require b < 1992. So n > 2. But 83² = 6889 > 1993, so b must divide 24. Hence b = 2, 3, 4, 6, 8, 12, or 24. But we can easily check that none of these work:

1 + 2 + 22 + ... + 29 = 1023, 1 + ... + 210 = 2047.

1 + 3 + ... + 36 = 1093, 1 + ... + 3^7 = 3280

1 + 4 + ... + 45 = 1365, 1 + ... + 46 = 5461

1 + 6 + ... 64 = 1555, 1 + ... + 65 = 9331

1 + 8 + 82 + 83 = 585, 1 + ... + 84 = 4681

1 + 12 + 122 + 123 = 1885, 1 + ... + 124 = 22621

1 + 24 + 242 = 601, 1 + ... + 243 = 14425 

Problem 
A2 

ABCD is a cyclic quadrilateral. A circle whose center is on the side AB touches the other three sides. Show that AB = AD + BC. What is the maximum possible area of ABCD in terms of |AB| and |CD|?

Answer

(h/2 + k/2) √(hk/2 - h²/4), where h = |CD|, k = |AB|

Solution

Let the circle have center O on AB and radius r. Let ∠OAD = θ, ∠OBC = φ. Since ABCD is cyclic, ∠ADC = 180^o-φ, so ∠ODA = 90^o-φ/2. If AD touches the circle at X, then AD = AX + XD = r cot θ + r tan(φ/2). Similarly, BC = r cot φ + r tan(θ/2). Put t = tan(θ/2). Then cot θ = (1-t²)/2t, so cot θ + tan(θ/2) = (1+t²)/2t = 1/sin θ. Similarly for φ, so AD + BC = r/sin θ + r/sin φ = AO + OB = AB.

Suppose AD and BC meet at H (we deal below with the case where they are parallel). Then HCD and HAB are similar, so area HCD = (CD²/AB²) area HAB and area ABCD = (1 - CD²/AB²) area HAB. Also AB/CD = HA/HC = HB/HD = (HA+HB)/(HC+HD) = (HA+HB)/(HB-BC+HA-DA) = (HA+HB)/(HA+HB-AB). Hence HA+HB = AB²/(AB-CD), which is fixed. Now for fixed HA+HB we maximise the area of HAB by taking HA = HB and hence AD = BC.

Put h = CD, k = AB. So k cos θ + h = k. Hence cos θ = (1-h/k). Hence sin θ = √(2h/k - h²/k²). So area ABCD = ½(h+k) ½ k sin θ = (h/2 + k/2) √(hk/2 - h²/4) (*).

If AD and BC are parallel then A and B must lie on the circle, so that ∠DAB = ∠ABC = 90^o. But ABCD is cyclic, so it must be a rectangle. Hence AB = CD and area ABCD = k²/2. In this case (*) still gives the correct answer.

Thanks to Vivek Kumar Mehra

Problem A3

There is a bulb in each cell of an n x n board. Initially all the bulbs are off. If a bulb is touched, that bulb and all the bulbs in the same row and column change state (those that are on, turn off, and those that are off, turn on). Show that it is possible by touching m bulbs to turn all the bulbs on. What is the minimum possible value of m?

Answer

n odd, n is minimum
n even, n² is minimum

Solution

If n is odd, touch each bulb in the first column. Then bulbs in the first column are each switched n times, which is odd and so end up on. All other bulbs are switched just once, and so end up on. n is obviously minimal, because if m < n, then there is a bulb which is not switched at all (there must be a column with no bulb touched and a row with no bulb touched, so the bulb in that column and row is not switched).

In n is even, touch each bulb. Then each bulb is switched 2n-1 times, so ends up on. We show that it is not possible to do better.

Note first that there is no benefit in touching a bulb more than once, so each must be touched zero of one times. Thus we can represent the scheme as an array of 0s and 1s, where 0 means that the corresponding bulb is not touched, and 1 means that it is touched.

Let A, B, C, D be four values at the corners of a rectangle. We claim that A+B has the same parity as C+D. Let L_AB be the number of 1s in the row AB are touched, similarly L_BC (the number of 1s in the column BC), L_CD, L_DA. Since bulb A is switched we must have L_AB + L_DA + A odd (note that L_AB + L_DA double-counts the no. of touches of A). Similarly, L_BC + L_CD + C is odd, so A + C + (L_AB + L_BC + L_CD + L_DA) is even. Similarly, considering B and D, we find that B + D + (L_AB + L_BC + L_CD + L_DA) is even, so A+C and B+D have the same parity. Adding B+C to both, we get that A+B and C+D have the same parity. It follows that either A = D and B = C, or A ≠ D and B ≠ D.

Keeping A and B fixed, we can now vary C (and hence D). It follows that either the row through B matches that through A, or it has every cell different (to the corresponding cell in row A). Similarly for the other rows. So we have k rows of one type and n-k rows which are equal to its "complement". Suppose first that k = n, so that all rows are the same. If we have all 1s, then we have a solution. If we have all 0s, we obviously do not have a solution. So suppose there is a 0 and a 1 in each row. Then the total count at a 1 is n-1 higher than at a 0 (because of the extra n-1 1s in the same column). So they cannot both be odd (because n is even). Contradiction.

Finally suppose there is a row and a complement row. So position A in one is 1, then position B in the same column in the other has 0. If a row has h 1s, then a complement row has n-h 1s. The column has z 1s, so A has z+h-1 or z+n-h-1 1s, and B has z+h or z+n-h 1s. But since n is even, z+h and z+n-h have the same parity, so A and B have opposite parity. Contradiction. So the only solution for n even is all 1s. 

Problem B1

ABC is an acute-angled triangle. P is a point inside its circumcircle. The rays AP, BP, CP intersect the circle again at D, E, F. Find P so that DEF is equilateral.

Solution

Let the angle bisector of A meet BC at A'. Let the perpendicular bisector of AA' meet the line BC at X. Take the circle center X through A and A'. Similarly, let the angle bisector of B meet AC at B' and let the perpendicular bisector of BB' meet the line AC at Y. Take the circle center Y through B and B'. The two circles meet at a point P inside the triangle, which is the desired point.

PAB and PED are similar, so DE/AB = PD/PB. Similarly, DF/AC = PD/PC, so DE/DF = (AB/AC)(PC/PB). Thus we need PB/PC = AB/AC. So P must lie on the circle of Apollonius, which is the circle we constructed with center X. Similarly, it must lie on the circle of Apollonius with center Y and hence be one of their points of intersection. It also lies on the third circle and hence we choose the point of intersection inside the triangle.

 Problem B2

n and r are positive integers. Find the smallest k for which we can construct r subsets A₁, A₂, ... , A_r of {0, 1, 2, ... , n-1} each with k elements such that each integer 0 ≤ m < n can be written as a sum of one element from each of the r subsets.

Answer

smallest integer such that k^r ≥ n.

Solution

We can form at most k^r distinct sums, so k^r must be ≥ n.

Now consider A₁ = {0, 1, 2, ... , k-1}, A₂ = {0, k, 2k, ... , (k-1)k}, A₃ = {0, k², 2k², ... , (k-1)k²}, ... , A_r = {0, k^r-1, 2k^r-1, ... , (k-1)k^r-1}. Then for any non-negative integer m < k^r, we can write m with r digits in base k (using leading zeros as necessary) and hence as a sum of one element from each A_i. This subset works for (k-1)k^r-1 < n ≤ k^r. For smaller n above (k-1)^r we cannot use all the elements given above, but we do not need them, so we just replace the elements which are too large by arbitrary elements under n.

For example, suppose n = 17, r = 4. We need k = 3. So we form A₁ = {0, 1, 2}, A₂ = {0, 3, 6}, A₃ = {0, 9, 18}, A₄ = {0, 27, 54}. Now 18, 27, 54 are unnecessary, so we pad out A₃ and A₄ with other elements. We could take A₃ = {0, 1, 9}, A₄ = {0, 1, 2}.

[Read More...]