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 = 120o. 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 an is defined as follows: a1 = 56, an+1 = an - 1/an. Show that an < 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 an be the first number remaining after n iterations, so a0 = 1, a1 = 2, a3 = 3, a4 = 5 etc. We claim that:
an+1 = 3/2 an if an is even, andWe use induction on n. Suppose an = 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 an = 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.
3/2 (an + 1) - 1 if an is odd.
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 = 120o. 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 = 120o and ∠MBN = 60o, 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) = 30o = ∠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 = 90o, 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 an is defined as follows: a1 = 56, an+1 = an - 1/an. Show that an < 0 for some n such that 0 < n < 2002.
Solution
Note that whilst an remains positive we have a1 > a2 > a3 > ... > an. Hence if am and am+n are in this part of the sequence, then am+1 = am - 1/am, am+2 = am+1 - 1/am+1 < am+1 - 1/am = am - 2/am. By a trivial induction am+n < am - n/am.
If we use one step then we need 562 = 3136 terms to get a1+3136 < 56 - 562/56 = 0, which is not good enough. So we try several steps.
Thus suppose that an > 0 for all n<= 2002. Then we get successively:
a337 < 56 - 336/56 = 50
a837 < 50 - 500/50 = 40
a1237 < 40 - 400/40 = 30
a1537 < 30 - 300/30 = 20
a1737 < 20 - 200/20 = 10
a1837 < 10 - 100/10 = 0.
Contradiction. So we must have an < 0 for some n < 2002.
Using Maple, we find that an 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 ... 2The 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.
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
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 xIf follows that P can also win from the four positions below (**):
P x x P x
x x R x x
x P x x P
x x x P x
x x x P x x xFor 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:
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
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 xThe 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.
P z x
x x R
w x P xR 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.
x R z x
x y x P
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
Labels:
Iberoamerican Mathematical Olympiad
Previous Article
