Solutions for June, 2002 problems

Solutions for June, 2002 problems

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 1. With y = x + 2n, the given equation can be rewritten as

(y-1)(y-2) ¼(y-2n) + (y+1)(y+2) ¼(y+2n) = 0 .

When the left side is expanded, the coefficients of the odd powers of y cancel out, and we get a sum involving only even powers of y with positive coefficients. Hence the left side must be positive for all real values of y, and so there is not real solution for the equation (and for the given equation in x).

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

|x | < 2k + 1 = 4k - 2k + 1 £ 4n - 4 - 2k + 1 < 4n - (2k + 1) < 4n + x = x + 4n

|x + 1 | < 2k < 4n - 1 + x = x + 4n - 1

¼ |x + 2k - 1 | < x + 4n - 2k .

(Draw a diagram of the real line.) Multiplying all the inequalities yields that |A | < |B | = B, so that A + B cannot vanish.

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).

Solution. First it will be established that if the binary representation of a number n has two consecutive ones and an even number of zeros in its rightmost positions, the number cannot be written as the sum of two perfect squares. For, all such numbers n must have the form 4^k(4s + 3). Suppose, if possible, that such a number can be written as the sum of two squares: n = x² + y². Using the fact that squares, modulo 4, are congruent to 0 or 1, we see that when n is odd the representation is impossible, while if n is even, both x and y must be even as well and (n/4) = (x/2)² + (y/2)². We can apply the same argument to (n/4) and continue dividing by 4 until we get a representation of 4s + 3. But this yields a contradiction.

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.

Solution. (a) Consider 20 consecutive numbers such that the smallest of them has units digit 0, and tens digit other than 9. Then, if S equals the sum of the digits of the smallest number, then the sums of the digitis of the 20 numbers are, in turn, S, S+1, ¼, S+9, S+1, ¼, S + 10. These include 11 consecutive numbers, one of which must be divisible by 11.

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.

(a) Solution. There are many ways of proving the formula. Two standard ways are to use induction and to make use of the identity (j+1)³ = j³ + 3j² + 3j + 1 summed for 1 £ j £ n. Y.Yang gives a geometric argument. Place unit cubical blocks in a pyramidic array with n² blocks at the bottom level, (n-1)² blocks at the next level, and so on, until there is a single block at the top. Inscribe this in a square-based right pyramid, whose slant edges pass through the upper outer corner of each level of cubes. This pyramid has a base with side length n+1 and a height n+1. The sum of the first n squares is equal to the volume of the cubes, which in turn is equal to the volume of the circumscribed pyramid less the volume of the space within the pyramid not occupied by the cubes.

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

(n+1)³ -

(n+1) -

n(n+1) =

(n+1)[2(n+1)² - 2 - 3n] =

(n+1)(2n² + n) =

n(n+1)(2n+1) .

(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

x₁ = 2 , y₁ = 1

x_n+1 = 2x_n + 3y_n , y_n+1 = x_n + 2y_n .

The smallest solutions of this equation are (x, y) = (1, 0), (2, 1), (7, 4), (26, 15), (97, 56), (362, 209),(1351, 780). Of these, only (7, 4) and (1351, 780) have the desired properties, and these correspond to (n, m) = (1, 1) and (337, 195). The first gives the trivial case, and the second gives the minimum value 337 of n.

155.

Find all real numbers x that satisfy the equation

3^{[(1/2) + log₃(cosx + sinx)]} - 2^{log₂(cosx - sinx)} = Ö2 .

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

Solution. By the definition and properties of the logarithmic function, it follows that (1) the domain of the equation is the set of all x for which cosx + sinx > 0 and cosx - sinx > 0, and that (2) 3^{log₃ M} = M when M > 0.

The given equation is equivalent to

Ö3 (cosx + sinx) - (cosx - sinx) = Ö2

Û (Ö3 - 1)cosx +(Ö3 + 1)sinx = Ö2

Ö6 - Ö2

cosx+

Ö6 + Ö2

sinx =

Noting that (Ö6-Ö2)/4 = sin15^° and (Ö6+Ö2)/4 = cos15^°, we see that the equation is equivalent to sin(x + 15^°) = ¹/₂, whose solutions are x = 15^° + k360^° and x = 165^° + k360^° for integers k, The latter family are extraneous, so only the former family constitute the solutions to the given problem.

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.

Solution. First, note that the point M is inside the triangle ABC when ÐA is acute and outside the triangle when ÐA is obtuse. Indeed, ÐA = ÐMAB + ÐMAC = ÐMCA + ÐMBA < 90^° implies that in the quadrilateral AMBC, ÐBMC > 180^°, which means that the point M is inside the triangle. Similarly, ÐA > 90^° implies that, in the quadrilateral ABMC, ÐBMC < 180^°; thus, the point M is outside the triangle. The same reasoning can be applied to determine whether the points N and P are inside or outside of the triangle ABC. It is straightforward to verify that when one of the angles is right, the respective point is on the side of the triangle opposite to the right angle.

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

BA¢:A¢C = BA²:AC²

and CB¢:B¢A = CB²:BA². Apply Ceva's Theorem to the lines AM, BN, CP to deduce from

AC¢

C¢B

BA¢

A¢C

CB¢

B¢A

AC²

CB²

BA²

AC²

CB²

BA²

= 1

that the lines AM, BN and CP are concurrent. Denote by K the intersection point of these lines and by O the circumcentre of the triangle ABC.

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.