location:

# Solutions

133.
Prove that, if a, b, c, d are real numbers, b ¹ c, both sides of the equation are defined, and

 ac - b2a - 2b + c = bd - c2b - 2c + d ,
then each side of the equation is equal to

 ad - bca - b - c + d .
Give two essentially different examples of quadruples (a, b, c, d), not in geometric progression, for which the conditions are satisfied. What happens when b = c?
Solution 1. The given condition is equivalent to

 0
 = (ac - b2)(b - 2c + d) - (bd - c2)(a - 2b + c)
 = (b-c)(ac - b2 + bd - c2) - [(ac - b2)(c - d) + (bd - c2)(a - b)]
Note that the quantity is square brackets vanishes when b = c, so that (b - c) should be a factor of it. Indeed, we have

 (ac - b2)(c - d) + (bd - c2)(a - b) = (b - c)(ad - bc) .
Since b ¹ c, we find that the given condition is equivalent to

 0 = (ac - b2) + (bd - c2) - (ad - bc)
or

 (ac - b2) + (bd - c2) = ad - bc .
It follows that

 ac - b2a - 2b + c
 = bd - c2b - 2c + d
 = (ac - b2) + (bd - c2)(a - 2b + c) + (b - 2c + d)
 = ad - bca - b - c + d ,
as desired. Note that, in the event that a - b - c + d = 0, we must have ad - bc = 0, as well. (Explain!)

A generic example is (a, b, c, d) = (rk-1 ±1,rk ±1, rk+1 ±1, rk+2 ±1), where r ¹ 0, 1 and k is arbitrary.

Suppose that b = c. If a ¹ b and d ¹ b, then both sides of the datum reduce to b, and the condition is a tautology. However, the final fraction need not be equal to b in this case: an example is (a, b, c, d) = (2, 1, 1, 3). On the other hand, suppose that a = b = c ¹ d. The one side of the datum is undefined, while we find that

 bd - c2b - 2c + d = b    and ad - bca - b - c + d = bd - b2d - b = b .
If a ¹ b = c = d, then we have a similar result. Finally, if a = b = c = d, then all fractions are undefined.

Solution 2. [A. Mao] Let

 k = ac - b2a - 2b + c = bd - c2b - 2c + d .
Then

 (a - k)(c - k) = ac - ak - ck + k2 = b2 - 2bk + k2 = (b - k)2
and

 (b - k)(d - k) = (c - k)2 .
Hence

 (a - k)(d - k)[(b - k)(c - k)] = [(b - k)(c - k)]2 .
Note that b = k Û c = k. Since b ¹ c, then both b and c must differ from k. Hence

 (a - k)(d - k) = (b - k)(c - k) Þad - bc = k(a - b - c + d) .
If a - b - c + d = 0, then ad - bc = 0 and the expression in the conclusion is undefined. Otherwise,

 ad - bca - b - c + d = k
and the result follows.

The given conditions imply that a - k, b - k, c - k, d - k are in geometric progresion. Conversely, pick u arbitrary and r ¹ 0, 1, and let (a, b, c, d) = (k + u, k + ur, k + ur2, k + ur3) to obtain a generic example.

Comments. Here are some numerical examples provided by various solvers for (a, b, c, d): (1, 2, 5, 14), (1, 5, 3, 4), (2, 6, 12, 21), (5, 9, 1, 17), (8, 24, 12, 21). Note that, when (a, b, c, d) = (a, b, a, b), both sides of the datum equal 1/2(a + b), while the fraction in the conclusion is undefined.

The given condition is equivalent to

 0 = (b - c)(ac + bd + bc - ad - b2 - c2) ,
from which (ac - b2) + (bd - c2) = ad - bc, and we can proceed as in Solution 1.

Very few full marks were given for this problem, as solvers were not careful about details. Whenever an expression appears in a denominator or you cancel a factor out of a product, you must consider the possibility that it might vanish. Most people ignored this possibility. In addition, the analysis of the situation when b = c was not at all thorough.

134.
Suppose that

 a = zb + yc

 b = xc + za

 c = ya + xb .
Prove that

 a21 - x2 = b21 - y2 = c21 - z2 .
Of course, if any of x2, y2, z2 is equal to 1, then the conclusion involves undefined quantities. Give the proper conclusion in this situation. Provide two essentially different numerical examples.
Solution. Suppose, say, that x2 = 1. Then x = ±1, whence za = b c and ya = c b. Thus a(y ±z) = 0. Suppose a = 0; then b2 = c2. If b = c = 0, then b2(1 - z2) = c2(1 - y2). If bc ¹ 0, then |zb | = |yc | implies that z2 = y2, in which case b2(1 - z2) = c2(1 - y2).

On the other hand, suppose that x2 = 1 and a ¹ 0. Then y ±z = 0, so that

 a = z(b ±c) = az2
whence z2 = y2 = x2 = 1. Since a ¹ 0, it is not possible for both b and c to vanish. Let b ¹ 0. Then

 c - xb = ya = yzb + y2c = yzb + c
so that x = -yz. In this case, all the expressions in the conclusion are undefined.

We now suppose that none of x2, y2, z2 is equal to 1. >From b = xc + za and xc = xya + x2b, we deduce that

 (1 - x2)b = (xy + z)a .
Since x2 ¹ 1, we have that xy + z ¹ 0, and so

 a21 - x2 = abxy + z .
>From c = ya + xb and xb = x2c + xza, we deduce that

 (1 - x2)c = (xz + y)a ,
whence

 a21 - x2 = acxz + y .
>From a = zb + yc and zb = xzc + z2a, we deduce that

 (1 - z2)a = (xz + y)c ,
whence

 c21 - z2 = acxz + y = a21 - x2 .
>From a = zb + yc and yc = y2a + xyb, we deduce that

 (1 - y2)a = (xy + z)b ,
whence

 b21 - y2 = abxy + z = a21 - x2 .
The result now follows.

Comments. Other interesting conclusions can be drawn. Adding and subtracting the first two equations, we have that

 (a - b)(1 + z) = (y - x)c

 (a + b)(1 - z) = (y + x)c
so that

 (a2 - b2)(1 - z2) = (y2 - x2)c2

 Þ c21 - z2 = a2 - b2y2 - x2 .
Similarly

 b21 - y2 = c2 - a2x2 - z2 and a21 - x2 = b2 - c2z2 - x2 .

Also, since (xy + z)a = (1 - x2)b and (xz + y)a = (1 - x2)c, we have that

 (1 - x2)a = (1 - x2)(zb + yc) = (2xyz + z2 + y2)aÞ a(x2 + y2 + z2 + 2xyz) = a .
Similarly, b(x2 + y2 + z2 + 2xyz) = b and c(x2 + y2 + z2+ 2xyz) = c. For each solution of the given system for which not all of a, b, c vanish, we must have x2 + y2 + z2 + 2xyz = 1.

Since xc = b - za and xb = c - ya, it follows that b2 - zab = c2 - yac, so that

 bz - yc = b2 - c2a and   bz + yc = a .
Hence

 z = a2 + b2 - c22ab and   y = a2 + c2 - b22ac .
Also,

 x = b2 + c2 - a22bc .
If a, b, c are the sides of a triangle ABC, then we have

 cos2 A + cos2 B + cos2 C + 2cosA cosB cosC = 1 .
[Can you prove this directly?]

Here are some examples of sextuples (a, b, c; x, y, z): (a, b, c; cosA, cosB, cosC), (1, 3, 6; [11/9],7/3, -[13/3]), (2, 5, 9; [17/15],5/3, -[13/5]), (-5, 5, 0; 4, 4, -1).

135.
For the positive integer n, let p(n) = k if n is divisible by 2k but not by 2k+1. Let x0 = 0 and define xn for n ³ 1 recursively by

 1xn = 1 + 2p(n) - xn-1 .
Prove that every nonnegative rational number occurs exactly once in the sequence { x0, x1, x2, ¼, xn, ¼}.
Comment. This problem of Donald E. Knuth was posed in a recent issue of the American Mathematical Monthly.

Solution. An examination of the table of values leads to the conjectured recursions:

 x2k+1 = xk + 1                 (for k ³ 0) ,

 1x2k = 1xk + 1                 (for k ³ 1) .
Since (x0, x1, x2) = (0, 1, 1/2), this equation holds for the lowest value of k. We use an induction argument. Suppose k ³ 1 and that x2k - 1 = xk-1 + 1. Then

 1x2k
 = 1 + 2p(2k) - x2k-1
 = 1 + 2[1 + p(k)] - (xk-1 + 1)
 = 1 + (1 + 2p(k) - xk-1) = 1 + 1xk
and

 1x2k+1 = 1 - x2k = 1 - xkxk + 1 = 1xk + 1
so that x2k+1 = xk + 1. The desired recursions follow.

>From the two recursions, we see that xn > 1 when n is odd and exceeds 1 and xn < 1 when n is even and exceeds 0. Thus, the values x0 = 0 and x1 = 1 are assumed only once. Suppose, if possible, that some rational is assumed twice. Let r be the smallest index for which xr = xs for some s > r ³ 2. Then r and s must have the same parity and it follows from the recursions that xër/2 û = xës/2 û, contradicting the minimality of r. Hence, no value of xn is assumed more than once.

It is straightforward to see that, for each non-negative integer m,

 x2m - 1 = m         and           x2m = 1m+1 .
Also, suppose that xu xv = 1. Then

 1x2v = 1xv + 1 = xu + 1 = x2u+1
so that x2u+1x2v = 1.

Let m be a positive integer. We show that, for 0 £ k £ 2m- 1, i = 2m + k and j = 2m+1 - (k+1), xi xj = 1. This is clearly true for m = 1, since x2 x3 = 1. Suppose that it has been established for some particular value of m ³ 1. We show that it holds for m replaced by m+1.

Let 0 £ l £ 2m+1 - 1, i = 2m+1 + l = 2m+2 -(2m+1 - l) and j = 2m+2 - (l + 1) = 2m+1 + (2m+1 - l - 1). Since i and j have opposite parity and can be put into either form, we may suppose wolog that l = 2r is even, whereupon i = 2v is even and j = 2u + 1 is odd. Thus v = 2m + r and u = 2m - (r + 1), so that by the induction hypothesis, xu xv = 1, whence it follows that xi xj = x2vx2u+1 = 1. The desired result follows by induction.

This shows that the set S of positive rationals of the form xn contains 0, 1 and is closed under each of the operations x ® x+1 and x ® 1/x. Thus S contains all nonnegative integers. Suppose we have shown that S contains all positive rationals with denominators not exceeding s. Consider a rational p/(s+1) with 1 £ p £ s. By the induction hypothesis, (s+1)/p Î S, so that p/(s+1) Î S. Hence, for each nonnegative integer t,

 p(s+1) + t = p + (s+1)ts+1 Î S ,
and so we can conclude that every positive rational with denominator s+1 belongs to S. Hence, by induction, we see that S contains every rational.

136.
Prove that, if in a semicircle of radius 1, five points A, B, C, D, E are taken in consecutive order, then

 |AB |2 + |BC |2 + |CD |2 +|DE |2 + |AB ||BC ||CD |+ |BC ||CD ||DE | < 4 .
Comment. The inequality is strict except in certain degenerate cases in which the points are not all distinct.

Solution 1. If A and E are shifted to the ends of the diameter, then the left side is at least as large. Thus, it suffices to prove the result when AE is a diameter. Let |AB | = a, |BC | = b, |CD | = c, |DE | = d, |AC | = u and |CE | = v. Observe that v > c and u > b [why?]. Suppose a = ÐCAE and b = ÐCEA. Then ÐABC = 180° - b and ÐCDE = 180° -a. We have |AE | = 2, and

 u2 = a2 + b2 + 2abcosb = a2 + b2 + abv > a2 + b2 + abc
and

 v2 = c2 + d2 + 2cdcosa = c2 + d2 + cdu > c2 + d2 + bcd .
Hence

 a2 + b2 + c2 + d2 + abc + bcd < u2 + v2 = 4 .

Solution 2. [A. Mao] As in Solution 1, we reduce to the case that AE is a diameter. Use the same notation as in Solution 1, and let |AD | = p and |BE | = q. Note that ÐABE = ÐACE = ÐADE = 90°. By Ptolemy's Theorem, we have that

 |BC ||AE |
 + |AB ||CE | = |AC ||BE |
 Þ 2b + av = uq = _____Ö4 - v2 _____Ö4 - a2
 Þ 4b2 + 4bav = 16 - 4a2 - 4v2
 Þ a2 + b2 + v2 + abv = 4 .
Similarly, c2 + d2 + u2 + cdu = 4. Adding and using u2 + v2 = 4, we obtain that

 a2 + b2 + c2 + d2 + abv + cdu = 4 .
Since triangles ABC and CDE are obtuse with the largest angles at B and D respectively, c = |CD | < |CE | = v and a < u, so that

 a2 + b2 + c2 + d2 + abc + bcd < 4 .

137.
Can an arbitrary convex quadrilateral be decomposed by a polygonal line into two parts, each of whose diameters is less than the diameter of the given quadrilateral?
Solution. No. Let ABC be an equilateral triangle, and let D be an exterior point in the region bounded by AC and the circle with centre B and radius AB. Then the diameter of the quadrilateral ABCD is |AB | = |BC | = |CA |. Any partition of the quadrilateral ABCD into two parts must have one of the parts containing two of the three points A, B, C; the diameter of this part is equal to that of ABCD.

138.
(a) A room contains ten people. Among any three. there are two (mutual) acquaintances. Prove that there are four people, any two of whom are acquainted.
(b) Does the assertion hold if ``ten'' is replaced by ``nine''?
Solution. Observe that the members of any pair each not acquainted with some third person must be acquainted with each other. It follows that the pairs of any group of people, each not acquainted with a particular outside person, must be mutual acquaintances.

We first show that, if any individual, say A, is acquainted with at least six people, B, C, D, E, F, G, then the conclusion follows. Suppose, B, say, does not know C, D, E, then each pair of A, C, D, E must be acquainted. On the other hand, if B knows each of C, D, E, then, as two of C, D, E know each other, say C and D, then each pair of A, B, C, D must be acquainted. Since any person acquainted with A must either be acquainted with or not be acquainted with three other people acquainted with A, the result follows.

(a) When there are ten people, each person either is not acquainted with four of the others (who then make a set of four each pair of which are acquaintances) or must be acquainted with at least six of the others, in which case we get the result by the previous paragraph.

(b) The assertion holds for nine people. In this case, each person either is not acquainted with four of the others or must be acquainted with at least five of the others. Suppose that each person is acquainted with at least five of the others. Then, adding together the number of acquaintances of each of the nine people, we get a sum of at least 9 ×5 = 45. But, each pair of acquaintances is counted twice, so the sum must be even and so be at least 46. But then there must be someone with at least six acquaintances, and we can obtain the desired result.

 haut de la page | contactez-nous | confidentialité | plan du site |