A1. Let f(x) = xn + 5xn-1 + 3, where n > 1 is an integer. Prove that f(x) cannot be expressed as the product of two non-constant polynomials with integer coefficients.
A2. Let D be a point inside the acute-angled triangle ABC such that ∠ADB = ∠ACB + 90o, and AC·BD = AD·BC. (a) Calculate the ratio AB·CD/(AC·BD).
(b) Prove that the tangents at C to the circumcircles of ACD and BCD are perpendicular.
A3. On an infinite chessboard a game is played as follows. At the start n2 pieces are arranged in an n x n block of adjoining squares, one piece on each square. A move in the game is a jump in a horizontal or vertical direction over an adjacent occupied square to an unoccupied square immediately beyond. The piece which has been jumped over is removed. Find those values of n for which the game can end with only one piece remaining on the board.
B1. For three points P, Q, R in the plane define m(PQR) as the minimum length of the three altitudes of the triangle PQR (or zero if the points are collinear). Prove that for any points A, B, C, X: m(ABC) ≤ m(ABX) + m(AXC) + m(XBC).
B2. Does there exist a function f from the positive integers to the positive integers such that f(1) = 2, f(f(n)) = f(n) + n for all n, and f(n) < f(n+1) for all n?
B3. There are n > 1 lamps L0, L1, ... , Ln-1 in a circle. We use Ln+k to mean Lk. A lamp is at all times either on or off. Initially they are all on. Perform steps s0, s1, ... as follows: at step si, if Li-1 is lit, then switch Li from on to off or vice versa, otherwise do nothing. Show that: (a) There is a positive integer M(n) such that after M(n) steps all the lamps are on again;
(b) If n = 2k, then we can take M(n) = n2 - 1.
(c) If n = 2k + 1, then we can take M(n) = n2 - n + 1.
Solutions
Problem A1
Let f(x) = xn + 5xn-1 + 3, where n > 1 is an integer. Prove that f(x) cannot be expressed as the product of two non-constant polynomials with integer coefficients.
Solution
Suppose f(x) = (xr + ar-1xr-1 + ... + a1x ± 3)(xs + bs-1xs-1 + ... + b1x ± 1). We show that all the a's are divisible by 3 and use that to establish a contradiction.
First, r and s must be greater than 1. For if r = 1, then ± 3 is a root, so if n is even, we would have 0 = 3n ± 5·3n-1 + 3 = 3n-1( 3 ± 5) + 3, which is false since 3 ± 5 = 8 or -2. Similarly if n is odd we would have 0 = 3n-1(±3 + 5) + 3, which is false since ±3 + 5 = 8 or 2. If s = 1, then ±1 is a root and we obtain a contradiction in the same way.
So r ≤ n - 2, and hence the coefficients of x, x2, ... , xr are all zero. Since the coefficient of x is zero, we have: a1 ± 3b1 = 0, so a1 is divisible by 3. We can now proceed by induction. Assume a1, ... , at are all divisible by 3. Then consider the coefficient of xt+1. If s-1 ≥ t+1, then at+1 = linear combination of a1, ... , at ± 3bt+1. If s-1 < t+1, then at+1 = linear combination of some or all of a1, ... , at. Either way, at+1 is divisible by 3. So considering the coefficients of x, x2, ... , xr-1 gives us that all the a's are multiples of 3. Now consider the coefficient of xr, which is also zero. It is a sum of terms which are multiples of 3 plus ±1, so it is not zero. Contradiction. Hence the factorization is not possible.
Problem A2
Let D be a point inside the acute-angled triangle ABC such that ∠ADB = ∠ACB + 90o, and AC·BD = AD·BC.
(a) Calculate the ratio AB·CD/(AC·BD).
(b) Prove that the tangents at C to the circumcircles of ACD and BCD are perpendicular.
Solution
By Glen Ong, Oracle Corporation
Take B' so that CB = CB', ∠BCB' = 90o and B' is on the opposite side of BC to A. It is easy to check that ADB, ACB' are similar and DAC, BAB' are similar. Hence AB/BD = AB'/B'C and CD/AC = BB'/AB'. It follows that the ratio given is BB'/B'C which is √2.
Take XD the tangent to the circumcircle of ADC at D, so that XD is in the ∠ADB. Similarly, take YD the tangent to the circumcircle BDC at D. Then ∠ADX = ∠ACD, ∠BDY = ∠BCD, so ∠ADX + ∠BDY = ∠ACB and hence ∠XDY = ∠ADB - (∠ADX + ∠BDY) = ∠ADB - ∠ACB = 90o. In other words the tangents to the circumcircles at D are perpendicular. Hence, by symmetry (reflecting in the line of centers) the tangents at C are perpendicular.
Theo Koupelis, University of Wisconsin, Marathon provided a similar solution (about 10 minutes later!) taking the point B' so that ∠BDB' = 90o, BD = B'D and ∠B'DA = ∠ACB. DAC, B'AB are similar; and ABC, AB'D are similar.
Marcin Mazur, University of Illinois at Urbana-Champaign provided the first solution I received (about 10 minutes earlier!) using the generalized Ptolemy's equality (as opposed to the easier equality), but I do not know of a slick proof of this, so I prefer the proof above.
Problem A3
On an infinite chessboard a game is played as follows. At the start n2 pieces are arranged in an n x n block of adjoining squares, one piece on each square. A move in the game is a jump in a horizontal or vertical direction over an adjacent occupied square to an unoccupied square immediately beyond. The piece which has been jumped over is removed. Find those values of n for which the game can end with only one piece remaining on the board.
Solution
We show first that the game can end with only one piece if n is not a multiple of 3. Note first that the result is true for n = 2 or 4.
n=2
X X . . X . . X . . .n = 4
X X X X . . X . . .
X
X X X X XThe key technique is the following three moves which can be used to wipe out three adjacent pieces on the border provided there are pieces behind them:
X X X X X X . X X X . X . . X X . . X X . X . .
X X X X X X . X . . X X . . X X X . X X X . X X
X X X X X X X X X X X X X X X X . X X X . X X X
X X X X X X X X X X X X X X X X . X X X . X X X
X X X
. X . . . X . . . X X . . X . . . X . . . . . .
X X . . . . X . . . . . . . X . . X X . . . X .
. X X X . X X X . X . X . X . X . . . X . X . X
. X X X . X X X . X X X . X X X . . X X . . X X
. . . . . . . . . . . . . . . .
. . X X . X . . . . . . . . . .
. X . . . X . . . . . . . . . .
. . X . . . X . . X X . . . . X
X X X X X . X X . X X XWe can use this technique to reduce (r + 3) x s rectangle to an r x s rectangle. There is a slight wrinkle for the last two rows of three:
X X X X X . . . X . . .
X X
X X X X X X . X . . X X . . X X . . . X . . . XThus we can reduce a square side 3n+2 to a 2 x (3n+2) rectangle. We now show how to wipe out the rectangle. First, we change the 2 x 2 rectangle at one end into a single piece alongside the (now) 2 x 3n rectangle:
X X X X X X . X . . X X . . X X . . . X . . . X
. . . X . . X X . . X X . X . . . X X . . . . X
X X . . . .Then we use the following technique to shorten the rectangle by 3:
X X . . . .
X X X
X X X X . X X . X . . . . . .That completes the case of the square side 3n+2. For the square side 3n+1 we can use the technique for removing 3 x r rectangles to reduce it to a 4 x 4 square and then use the technique above for the 4 x 4 rectangle.
X X X X . X X . X . . . . . .
X X X X . X X . X . X
Finally, we use a parity argument to show that if n is a multiple of 3, then the square side n cannot be reduced to a single piece. Color the board with 3 colors, red, white and blue:
R W B R W B R W B ...
W B R W B R W B R ...
B R W B R W B R W ...
R W B R W B R W B ...
...
Let suppose that the single piece is on a red square. Let A be the
number of moves onto a red square, B the number of moves onto a white
square and C the number of moves onto a blue square. A move onto a red
square increases the number of pieces on red squares by 1, reduces the
number of pieces on white squares by 1, and reduces the number of pieces
on blue squares by 1. Let n = 3m. Then there are initially m pieces on
red squares, m on white and m on blue. Thus we have:
- A + B + C = m-1; A - B + C = m; A + B - C = m.
Solving, we get A = m, B = m - 1/2, C = m - 1/2. But the number of moves of each type must be integral, so it is not possible to reduce the number of pieces to one if n is a multiple of 3.
Problem B1
For three points P, Q, R in the plane define m(PQR) as the minimum length of the three altitudes of the triangle PQR (or zero if the points are collinear). Prove that for any points A, B, C, X:
m(ABC) ≤ m(ABX) + m(AXC) + m(XBC).
Solution
The length of an altitude is twice the area divided by the length of the corresponding side. Suppose that BC is the longest side of the triangle ABC. Then m(ABC) = area ABC/BC. [If A = B = C, so that BC = 0, then the result is trivially true.]
Consider first the case of X inside ABC. Then area ABC = area ABX + area AXC + area XBC, so m(ABC)/2 = area ABX/BC + area AXC/BC + area XBC/BC. We now claim that the longest side of ABX is at most BC, and similarly for AXC and XBC. It then follows at once that area ABX/BC ≤ area ABX/longest side of ABX = m(ABX)/2 and the result follows (for points X inside ABC).
The claim follows from the following lemma. If Y lies between D and E, then FY is less than the greater than FD and FE. Proof: let H be the foot of the perpendicular from F to DE. One of D and E must lie on the opposite side of Y to H. Suppose it is D. Then FD = FH/cos HFD > FH/cos HFY = FY. Returning to ABCX, let CX meet AB at Y. Consider the three sides of ABX. By definition AB ≤ BC. By the lemma AX is smaller than the larger of AC and AY, both of which do not exceed BC. Hence AX ≤ BC. Similarly BX ≤ BC.
It remains to consider X outside ABC. Let AX meet AC at O. We show that the sum of the smallest altitudes of ABY and BCY is at least the sum of the smallest altitudes of ABO and ACO. The result then follows, since we already have the result for X = O. The altitude from A in ABX is the same as the altitude from A in ABO. The altitude from X in ABX is clearly longer than the altitude from O in ABO (let the altitudes meet the line AB at Q and R respectively, then triangles BOR and BXQ are similar, so XQ = OR·BX/BO > OR). Finally, let k be the line through A parallel to BX, then the altitude from B in ABX either crosses k before it meets AX, or crosses AC before it crosses AX. If the former, then it is longer than the perpendicular from B to k, which equals the altitude from A to BO. If the latter, then it is longer than the altitude from B to AO. Thus each of the altitudes in ABX is longer than an altitude in ABO, so m(ABX) > m(ABO).
Problem B2
Does there exist a function f from the positive integers to the positive integers such that f(1) = 2, f(f(n)) = f(n) + n for all n, and f(n) < f(n+1) for all n?
Answer
Yes: f(n) = [g*n + ½], where g = (1 + √5)/2 = 1.618 ... .
Solution
This simple and elegant solution is due to Suengchur Pyun
Let g(n) = [g*n + ½]. Obviously g(1) = 2. Also g(n+1) = g(n) + 1 or g(n) + 2, so certainly g(n+1) > g(n).
Consider d(n) = g* [g*n + ½] + ½ - ( [g*n + ½] + n). We show that it is between 0 and 1. It follows immediately that g(g(n)) = g(n) + n, as required.
Certainly, [g*n + ½] > g*n - ½, so d(n) > 1 - g/2 > 0 (the n term has coefficient g2 - g - 1 which is zero). Similarly, [g*n + ½] ≤ g*n + ½, so d(n) ≤ g/2 < 1, which completes the proof.
I originally put up the much clumsier result following:
Take n = brbr-1 ... b0 in the Fibonacci base. Then f(n) = brbr-1 ... b00. This satisfies the required conditions.
Let u0 = 1, u1 = 2, ... , un=un-1+un-2, ... be the Fibonacci numbers. We say n = brbr-1 ... b0 in the Fibonacci base if br = 1, every other bi = 0 or 1, no two adjacent bi are non-zero, and n = brur + ... + b0u0. For example, 28 = 1001010 because 28 = 21 + 5 + 2.
We have to show that every n has a unique expression of this type. We show first by induction that it has at least one expression of this type. Clearly that is true for n = 1. Take ur to be the largest Fibonacci number ≤ n. Then by induction we have an expression for n - ur. The leading term cannot be ui for i > r - 2, for then we would have n >= ur + ur-1 = ur+1. So adding ur to the expression for n - ur gives us an expression of the required type for n, which completes the induction.
We show that ur + ur-2 + ur-4 + ... = ur+1 - 1. Again we use induction. It is true for r = 1 and 2. Suppose it is true for r - 1, then ur+1 + ur-1 + ... = ur+2 - ur + ur-1 + ur-3 + ... = ur+2 - ur + ur - 1 = ur+2 - 1. So it is true for r + 1. Hence it is true for all r. Now we can prove that the expression for n is unique. It is for n = 1. So assume it is for all numbers < n, but that the expression for n is not unique, so that we have n = ur + more terms = us + more terms. If r = s, then the expression for n - ur is not unique. Contradiction. So suppose r > s. But now the second expression is at most us+1 - 1 which is less than ur. So the expression for n must be unique and the induction is complete.
It remains to show that f satisfies the required conditions. Evidently if n = 1 = u0, then f(n) = u1 = 2, as required. If n = ua1 + ... + uar, then f(n) = ua1+1 + ... + uar+1 and f(f(n)) = ua1+2 + ... + uar+2. So f(n) + n = (ua1 + ua1+1) + ... + (uar + uar+1) = f(f(n)).
Problem B3
There are n > 1 lamps L0, L1, ... , Ln-1 in a circle. We use Ln+k to mean Lk. A lamp is at all times either on or off. Initially they are all on. Perform steps s0, s1, ... as follows: at step si, if Li-1 is lit, then switch Li from on to off or vice versa, otherwise do nothing. Show that:
(a) There is a positive integer M(n) such that after M(n) steps all the lamps are on again;
(b) If n = 2k, then we can take M(n) = n2 - 1.
(c) If n = 2k + 1, then we can take M(n) = n2 - n + 1.
Solution
(a) The process cannot terminate, because before the last move a single lamp would have been on. But the last move could not have turned it off, because the adjacent lamp was off. There are only finitely many states (each lamp is on or off and the next move can be at one of finitely many lamps), hence the process must repeat. The outcome of each step is uniquely determined by the state, so either the process moves around a single large loop, or there is an initial sequence of steps as far as state k and then the process goes around a loop back to k. However, the latter is not possible because then state k would have had two different precursors. But a state has only one possible precursor which can be found by toggling the lamp at the current position if the previous lamp is on and then moving the position back one. Hence the process must move around a single large loop, and hence it must return to the initial state.
(b) Represent a lamp by X when on, by - when not. For 4 lamps the starting situation and the situation after 4, 8, 12, 16 steps is as follows:
X X X XOn its first move lamp n-2 is switched off and then remains off until each lamp has had n-1 moves. Hence for each of its first n-1 moves lamp n-1 is not toggled and it retains its initial state. After each lamp has had n-1 moves, all of lamps 1 to n-2 are off. Finally over the next n-1 moves, lamps 1 to n-2 are turned on, so that all the lamps are on. We show by induction on k that these statements are all true for n = 2k. By inspection, they are true for k = 2. So suppose they are true for k and consider 2n = 2k+1 lamps. For the first n-1 moves of each lamp the n left-hand and the n right-hand lamps are effectively insulated. Lamps n-1 and 2n-1 remain on. Lamp 2n-1 being on means that lamps 0 to n-2 are in just the same situation that they would be with a set of only n lamps. Similarly, lamp n-1 being on means that lamps n to 2n-2 are in the same situation that they would be with a set of only n lamps. Hence after each lamp has had n-1 moves, all the lamps are off except for n-1 and 2n-1. In the next n moves lamps 1 to n-2 are turned on, lamp n-1 is turned off, lamps n to 2n-2 remain off, and lamp 2n-1 remains on. For the next n-1 moves for each lamp, lamp n-1 is not toggled, so it remains off. Hence all of n to 2n-2 also remain off and 2n-1 remains on. Lamps 0 to n-2 go through the same sequence as for a set of n lamps. Hence after these n-1 moves for each lamp, all the lamps are off, except for 2n-1. Finally, over the next 2n-1 moves, lamps 0 to 2n-2 are turned on. This completes the induction. Counting moves, we see that there are n-1 sets of n moves, followed by n-1 moves, a total of n2 - 1.
- X - X
X - - X
- - - X
X X X -
(c) We show by induction on the number of moves that for n = 2k+ 1 lamps after each lamp has had m moves, for i = 0, 1, ... , 2k - 2, lamp i+2 is in the same state as lamp i is after each lamp has had m moves in a set of n - 1 = 2k lamps (we refer to this as lamp i in the reduced case). Lamp 0 is off and lamp 1 is on. It is easy to see that this is true for m = 1 (in both cases odd numbered lamps are on and even numbered lamps are off). Suppose it is true for m. Lamp 2 has the same state as lamp 0 in the reduced case and both toggle since their predecessor lamps are on. Hence lamps 3 to n - 1 behave the same as lamps 1 to n - 3 in the reduced case. That means that lamp n - 1 remains off. Hence lamp 0 does not toggle on its m+1th move and remains off. Hence lamp 1 does not toggle on its m+1th move and remains on. The induction stops working when lamp n - 2 toggles on its nth move in the reduced case, but it works up to and including m = n - 2. So after n - 2 moves for each lamp all lamps are off except lamp 1. In the next two moves nothing happens, then in the following n - 1 moves lamps 2 to n - 1 and lamp 0 are turned on. So all the lamps are on after a total of (n - 2)n + n + 1 = n2 + n + 1 moves.
Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999
, ISBN 189-8855-48-X
, ISBN 189-8855-48-X 
Labels:
IMO
Previous Article
