


Solution 2. [Y. Yang] Let A = x(x+1) ¼(x+2n1) and B = (x+2n+1)(x+2n+2) ¼(x+4n). It is clear that none of the numbers 0, 1, ¼, 2n1 , 2n + 1, ¼, 4n is a solution. Since A and B cannot simultaneously vanish for any value of x, A + B = 0 can occur only if one is positive and the other negative.
Suppose that A < 0. Then there must be an odd number of negative factors in A, so that 2k1 < x < 2k for some integer k Î [0, n1]. In this situation, the factors x, x+1, ¼, x+2k are negative and all the other factors involved in A and those in B are positive, so that B > 0. We show that the absolute value of A must be less than the absolute value of B by comparing pairs of factors.
For the positive factors of A, we have x + 2k + 1 < x + 2n + 1, x + 2k + 2 < x + 2n + 2, ¼, x + 2n  1 = x + 2k + (2n  2k  1) < x + 4n  2k  1 = x + 2n +(2n  2k  1). For the negative factors A, we have that



Suppose that B < 0. Then there are an odd number of negative factors in B, so that, for some positive k not exceeding n, 2n  2k < x < 2n  2k+ 1. Since A has all negative factors, we have that A > 0. As in the earlier case, it can be proved that A  > B , so that A + B cannot vanish. The desired result follows.
We show that the second player, Brenda, has a winning strategy: she should always play so that the resulting 4004 digit number has the form described in the foregoing paragraph.
Case 1: Suppose the first player, Andrew, writes only 0. Then Brenda writes 1 on the first three turns and then keeps writing 0. This will result in the base 2 number 010101000 ¼000 = 21 ·4^{1999}, which by the argument above cannot be written as the sum of two squares.
Case 2: Suppose on the other hand, at some point, Andrew inserts a 1. Brenda then writes 1 on her next term, and copies what Andrew writes thereafter. The result number will have the form of n in the first paragraph and so cannot be written as the sum of two squares. Brenda triumphs again.
Comment. As you will have noticed, the problem solved here differs from the one originally posed which said that Brenda was the winner if the final number could be written as the sum of two integer squares. This was our mistake, and, when discovered, was too late to correct. This changed the original problem to a much more difficult one. Nevertheless, some comments on the new problem will be provided as a good example of how advantage can be taken even from mistakes.
There is a simple and clear condition that some numbers cannot be written as a sum of two squares: it is enough to show that they are congruent to 3, modulo 4. The difficulty of the problem arises from the fact that if the number is not congruent to 3, it does not necessarily mean that it can be written as the sum of two squares. A theorem in number theory states that a positive integer can be written as the sum of two squares if and only if no prime congruent to 3, modulo 4, divides the number to an odd exponent.
For the problem solved above, it is enough to use the weaker condition and have Brenda ignore all numbers other than those congruent to 3 modulo 4 that are winning numbers for her. To solve the problem actually posed, it is not enough to consider only such numbers. It becomes a problem to connect the binary representation of a number to the number of its prime factors congruent to 3, modulo 4.
Two students, who sent their work on the problem posed, deserve recognition for their excellent ideas and results. Andrew Critch tried to come up with a strategy that eliminates the losing situations for Brenda. He succeeds in eliminating 2^{4003} such situations, out of all the 2^{4004} possible endgame scenarios. Leonid Chindelevitch goes further in exploring the problem, using a different approach. He realizes that the number 2002 in the problem is not sufficient for the algorithm of the game. By experimentation, he concludes that there is a winning strategy for Brenda in the case that every player writes 1, 2 or 4 numbers. (The first two cases simply require Brenda to write a zero every time, while the third one is a bit more complicated.) However, there is no such strategy for Brenda when each player writes three numbers. On the contrary, in this case, there is a winning strategy for Andrew. He starts with 1, and follows with 1 on each of his other two turns if Brenda write 0 on her first move. Otherwise, he follows with 1 on his second move if Brenda's first move is 1, and then imitates Brenda's second move on his third move. This yields one of the results: 101010, 101011, 101110, 101111, 111000, 111110, 111111 (in decimal: 42, 43, 46, 47, 56, 57, 62, 63), none of which is the sum of two integer squares.
In order to investigate the problem further, Leonid has designed an algorithm to verify the existence of a winning strategy with respect to the number n of moves for each player. Computer simulations reveal that, for the 1 £ n £ 15, Brenda has a winning strategy only for n = 1, 2, 4. Since the algorithm used is exponential, the time becomes quite large under increase of n; for n = 15, more than six hours are required. Leonid also tries to determine the probability for Brenda to lead the game for ending at a winning number, and comes up with the conclusion that the probability is less than 0.31 for large numbers such as 2002. Accordingly, he concludes that it is not likely that there is a winning strategy for such a game with a large number of moves. Isn't it great!
Bonus points will be given to students with reasonable ideas on this problem. For the others, the problem will not be taken into account in compiling their scores.
Among any 39 consecutive integers, we can always find 20 such numbers. All that is required is that at least 20 of the 39 numbers must have the same hundreds digit. If all 39 have the same hundreds digit, then this is so. Otherwise, there are two hundred digits involved, and, by the pigeonhole principle, there must be twenty with the same hundreds digit.
Comment. It is not easy to formulate new problems. This is why those solving part (a) were given a full score, and bonus points assigned to anyone providing a reasonable suggestion for (b). Here are some generalizations:
(1) Prove that, among any 20n + 39 consecutive natural numbers, there is one, the sum of whose digits is divisible by 11 + n. [H. Li]
(2) Prove that, among any 20k  1 consecutive natural numbers, there is one, the sum of whose digits is divisible by k + 9 for 1 £ k £ 10. (This is the same as (1) for n = 2, 3, 4, 5.)
(3) Prove that, among any 200k  1 consecutive natural numbers, there is one the sum of whose digits is divisible by k + 18 (1 £ k £ 5).
We are open to further suggestions. Send them along to Ms. Valeria Pandelieva, 641 Kirkwood Avenue, Ottawa, ON K1Z 5X5.
The volume of the circumscribing pyramid is ^{1}/_{3}(n+1)^{2}(n+1) = ^{1}/_{3}(n+1)^{3}. Now look at the leftover part. It consists of a small pyramid at the top, and at each level, 4 square corner pyramids and 4 triangular prisms. Calling the top level the zeroth, we find that at the kth level down, the volume of the leftover part is equal to 4 ·^{1}/_{3} ·(1/2)^{2} + 4 ·^{1}/_{2}(1/2)k = (1/3) + k. Summing this for 0 £ k £ n yields (1/3)(n+1) + (1/2)n(n+1), so that the total volume of all the cubes is

(b) Solution 1. The condition to be satisfied is (n+1)(2n+1) = 6m^{2} for some integer m. Since the right side is even, n be an odd number, say, 2k  1. The equation reduces to k(4k1) = 3m^{2}. Suppose, to begin with, k is a multiple of 3: k = 3s. Then s(12s  1) = m^{2}. Since s and 12s  1 are coprime, both must be squares, i.e., s = p^{2} and 12s  1 = q^{2} for some natural numbers p and q. But 12s  1 º 3 (mod 4) cannot be the square of a natural number. Thus, there is no solution in this case.
The other possibility is that 4k  1 is a multiple of 3; equivalently, k  1 is a multiple of 3 (why?), so that k = 3s + 1. Thus, (3s + 1)(4s + 1) = m^{2}. Since 3s + 1 and 4s + 1 are coprime (why?), 3s + 1 = p^{2} and 4s + 1 = q^{2} for some natural numbers p and q. We now check in turn all the odd squares of the form 4s + 1 until we come to one for which 3s + 1 is square. This leads us to 4s + 1 = 15^{2} and 3s + 1 = 13^{2}, so that s = 56, k = 169, n = 337.
Solution 2. It is required to find the smallest natural number n for which (n+1)(2n + 1) = 6m^{2}, for some positive integer m. We manipulate the equation to make use of the technique of completion of the square. The equation is equivalent to 16n^{2} + 24n + 8 = 48m^{2} or (4n+3)^{2}  1 = 3(4m)^{2}. Setting x = 4n + 3 and y = 4m, we see that we need to find solutions of the equation x^{2}  3y^{2} = 1 where x º 3 and y º 0 (modulo 4).
Noting that x^{2}  3y^{2} = (x + Ö3)(x  Ö3), and that 2^{2}  3 ·1^{2} = 1, we can deduce that the equation x^{2}  3y^{2} = 1 is satisfied by (x, y) = (x_{n}, y_{n}) where x_{n} +Ö3y_{n} = (2 + Ö3)^{n} for each nonnegative integer n. These solutions can be given through the recursion



The given equation is equivalent to



Comment. Most participants attempted this problem and dealt well with the trigonometric transformations. However, it is important to check all purported solutions against the given equation, because the derived equation becomes equivalent to the equation solved in the solution only in the presence of the restrictions on the domain. Many students neglected this.
Wolog, consider ÐC. Case 1: ÐC < 90^{°}. Let CP instersect the segment AB at C¢. Since PC¢ is the angle bisector of ÐAPB (ÐAPC¢ = ÐBPC¢ = ÐACB), it follows that AC¢:C¢B = AP:BP. The triangles APC and BPC are similar, so that AP:CP = AC:BC and BP:CP = BC:AC Þ AP:BP = AC^{2}:CB^{2}Þ AC¢:C¢B = AC^{2}:CB^{2}. Similarly, if AM intersects BC at M¢ and BN instersects AC at N", then


Since ÐAPB = 2ÐC = ÐAOB, the quadrilateral APOB is concyclic. Also, if the line PC¢ intersects the circumcircle of APOB at the point C", then this point C" is the midpoint of that arc AB not containing O (as PC¢ is the angle bisector of ÐAPB), and O is the midpoint of the other arc AB. Thus, OC" is the diameter of this circle and ÐOPC" = ÐOPC = 90^{°}. Since the point K is on the line PC, ÐOPK = 90^{°}, too; thus P is a point on the circle whose diamter is OK. Similarly, the points M and N are on the same circle. This circle contains all the points M, N, P, K, O, so that the intersection point of AM, BN and CP is on the circumcircle of MNP.
Case 2: ÐC = 90^{°}. In this case, the point P is on the hypotenuse AB (thus, it coincides with the point C¢ of Case 1), and is also the point where the altitude from C toAB intersects AB. By the similarity of the triangles ABC and APC, AP:AC = AC:AB, while, by the similarity of the triangles, BPC and ABC, it follows that PC:BC = BC:AB. Then AP:PC = AC^{2}:BC^{2}, which replaces the equation AC¢:C¢B = AC^{2}:BA^{2} of Case 1.The other two angles are acute, so that the remaining parts of the solution can be pursued as in Case 1.
Case 3: ÐC > 90^{°} Now the point C is outside of the triangle ABC, as well as the circumcentre O. The proof is similar to that of Case 1, and follows the same steps.
Sources: Problem 151 is from the Bulgarian magazine
Matematika Plus, 2001. Problems 152, 154, 155, 156 are from the
contest papers of the 2001 Winter and Spring National Mathematics
Contests for High School students in Bulgaria.