151.

Prove that, for any natural number n, the equation

x(x+1)(x+2)¼(x+2n-1) + (x+2n+1)(x+2n+2)¼(x+4n) = 0

does not have real solutions.

Solution 2. [Y. Yang] Let A = x(x+1) ¼(x+2n-1) and B = (x+2n+1)(x+2n+2) ¼(x+4n). It is clear that none of the numbers 0, 1, ¼, 2n-1 , 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 -2k-1 < x < -2k for some integer k Î [0, n-1]. 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.

152.

Andrew and Brenda are playing the following game. Taking turns, they write in a sequence, from left to right, the numbers 0 or 1 until each of them has written 2002 numbers (to produce a 4004-digit number). Brenda is the winner if the sequence of zeros and ones, considered as a binary number (i.e., written to base 2), cannot be written as the sum of two integer squares. Otherwise, the winner is Andrew. Prove that the second player, Brenda, can always win the game, and explain her winning strategy (i.e., how she must play to ensure winning every game).

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¹⁹⁹⁹, 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⁴⁰⁰³ such situations, out of all the 2⁴⁰⁰⁴ 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.

153.

(a) Prove that, among any 39 consecutive natural numbers, there is one the sum of whose digits (in base 10) is divisible by 11.

(b) Present some generalizations of this problem.

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.

154.

(a) Give as neat a proof as you can that, for any natural number n, the sum of the squares of the numbers 1, 2, ¼, n is equal to n(n+1)(2n+1)/6.

(b) Find the least natural number n exceeding 1 for which (1² + 2² + ¼+ n²)/n is the square of a natural number.

The volume of the circumscribing pyramid is ¹/₃(n+1)²(n+1) = ¹/₃(n+1)³. Now look at the left-over 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 left-over part is equal to 4 ·¹/₃ ·(1/2)² + 4 ·¹/₂(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² for some integer m. Since the right side is even, n be an odd number, say, 2k - 1. The equation reduces to k(4k-1) = 3m². Suppose, to begin with, k is a multiple of 3: k = 3s. Then s(12s - 1) = m². Since s and 12s - 1 are coprime, both must be squares, i.e., s = p² and 12s - 1 = q² 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². Since 3s + 1 and 4s + 1 are coprime (why?), 3s + 1 = p² and 4s + 1 = q² 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² and 3s + 1 = 13², 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², 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² + 24n + 8 = 48m² or (4n+3)² - 1 = 3(4m)². Setting x = 4n + 3 and y = 4m, we see that we need to find solutions of the equation x² - 3y² = 1 where x º 3 and y º 0 (modulo 4).

Noting that x² - 3y² = (x + Ö3)(x - Ö3), and that 2² - 3 ·1² = 1, we can deduce that the equation x² - 3y² = 1 is satisfied by (x, y) = (x_n, y_n) where x_n +Ö3y_n = (2 + Ö3)ⁿ for each nonnegative integer n. These solutions can be given through the recursion

155.

Find all real numbers x that satisfy the equation

3[(1/2) + log3(cosx + sinx)] - 2log2(cosx - sinx) = Ö2 .

[The logarithms are taken to bases 3 and 2 respectively.]

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.

156.

In the triangle ABC, the point M is from the inside of the angle BAC such that ÐMAB = ÐMCA and ÐMAC = ÐMBA. Similarly, the point N is from the inside of the angle ABC such that ÐNBA = ÐNCB and ÐNBC = ÐNAB. Also, the point P is from the inside of the angle ACB such that ÐPCA = ÐPBC and ÐPCB = ÐPAC. (The points M, N and P each could be inside or outside of the triangle.) Prove that the lines AM, BN and CP are concurrent and that their intersection point belongs to the circumcircle of the triangle MNP.

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²:CB²Þ AC¢:C¢B = AC²:CB². 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²:BC², which replaces the equation AC¢:C¢B = AC²:BA² 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.