Search

Solutions and comments



55.
A textbook problem has the following form: A man is standing in a line in front of a movie theatre. The fraction x of the line is in front of him, and the fraction y of the line is behind him, where x and y are rational numbers written in lowest terms. How many people are there in the line? Prove that, if the problem has an answer, then that answer must be the least common multiple of the denominators of x and y.
Solution. Let p and q be the denominators of x and y, when written in their lowest terms; each denominator has no positive divisor save 1 in common with the corresponding numerator. Let n be the number of people in line. Since xn and yn are integers, p and q must both divide n, so that n is a multiple of m, the least common multiple of p and q.

1 - x - y can be written as a fraction of the form u/m. Since (u/m)n = u(n/m) = 1, we must have that u = n/m = 1, so that in particular m = n.

Comment. This is quite a difficult question to write up, because you have to put your finger quite precisely on the main issues involved. Many solvers relied on statements that were equally if not more difficult to see than the result of the problem. The point of a solution is to show how a result can be obtained from simpler or more wellknown propositions.



56.
Let n be a positive integer and let x1, x2, ¼, xn be integers for which


x12 + x22 + ¼+ xn2 + n3 £ (2n-1)(x1 + x2 + ¼+ xn) + n2 .
Show that
(a) x1, x2, ¼, xn are all nonnegative;
(b) x1 + x2 + ¼+ xn + n + 1 is not a perfect square.
Solution 1. The inequality can be rewritten as


n
å
i=1 
(xi - n) (xi -
n - 1
 
) £ 0 .
(The line over n - 1 is a form of bracket.) Since each summand is positive for integers other than n and n-1, the inequality can hold only if each xi is equal to either n or n-1. Therefore,


n2 + 1 = n(n-1) + n + 1 £ x1 + x2 + ¼+ xn + n + 1 £ n2 + n + 1 < (n+1)2 .
Parts (a) and (b) follow easily from this.

Solution 2. [R. Furmaniak] Taking the difference between the right and left sides leads to the equivalent inequality


n
å
k=1 
[2xk - (2n-1)]2 £ n .
Since each term in the sum is odd, it can only be 1. Therefore 2xk - (2n-1) = ±1, whence xk is equal to n or n-1 for each k. The solution can be concluded as before.

Solution 3. [O. Bormashenko, M. Holmes] The given inequality is equivalent to


n
å
i=1 
xi(xi -
2n-1
 
) £ n2 - n3 .
Observe that, for each i,


xi(
2n-1
 
- xi) £ [ 1
2
(2n - 1)]2 = n2 - n + 1
4
 .
This is a consequence of the arithmetic-geometric means inequality when the left side is positive, and obvious when the left side is negative. Since xi is supposed to be an integer, we must have


xi(
2n-1
 
- xi) £ n2 - n
and equality occurs if and only if xi = n or xi = n-1. (One way to see this is to note that the left side is a quadratic and can take each of its values no more than twice.) Multiplying by -1 yields that


xi(xi -
2n-1
 
) ³ n - n2
whence


n
å
i=1 
xi(xi -
2n-1
 
) ³ n2 - n3 ,.
with equality if and only if each xi is equal to n or n-1. But because of the given inequality, equality does occur. The solution can now be completed as before.

Solution 4. The given inequality is equivalent to


n
å
i=1 
(n - xi)2 £ n
å
i=1 
(n - xi) .
(1)
However, since xi is an integer for each i, (n - xi)2 ³ (n - xi) with equality if and only if n - xi is equal to 0 or 1. Thus


n
å
i=1 
(n - xi)2 ³ n
å
i=1 
(n - xi)
(2)
with equality if and only if n - xi = 0 or 1 for each i. But (1) and (2) together imply that equality does occur for each i, whence xi is equal to either n or n-1. The solution is completed as before.



57.
Let ABCD be a rectangle and let E be a point in the diagonal BD with ÐDAE = 15°. Let F be a point in AB with EF ^AB. It is known that EF = 1/2AB and AD = a. Find the measure of the angle ÐEAC and the length of the segment EC.
Solution. We begin with the observation that tan15° = 2 - Ö3. (Exercise: Use either tanq = (sin2q)/(1 + cos2q)-1 or tanq = tan(3q- 2q) with q = 15°.) Let a and b be the respective lengths of AD and FE, so that |AF | = (2 - Ö3)b, |AB | = 2b and |FB | = Ö3b. Then tanÐFEB = Ö3, so that ÐFEB = ÐADB = 60°. Hence |BE | = 2b, |BD | = 2a and |ED | = 2(a - b). Since a/2b = cotÐADB = 1/Ö3, 3a2 = 4b2.

Since ÐDAC = ÐADB = 60° and ÐDAE = 15°, it follows that ÐEAC = 45°.

We can determine |EC | using the law of cosines in DDEC. Thus,


|EC |2
= 4b2 + 4(a - b)2 - 8(a - b)bÖ3/2
= 8b2 - 8ab + 4a2 - 4abÖ3 + 4b2Ö3
= 4b2(2 + Ö3) - 4ab(2 + Ö3) + 4a2
= 3a2(2 + Ö3) - 2a2Ö3(2 + Ö3)+ 4a2
= a2 (4 - Ö3)  ,
whence |EC | = aÖ{4 - Ö3}.

Comment. The length of EC can be found more straightforwardly by introducing an additional point. Produce the line FE to meet CD at G. Then EGC is a right triangle for which |EG | = a - b and |GC | = Ö3b. Applying pythagoras theorem yields


|EC |2 = a2 - 2ab + 4b2 = a2 - Ö3a2 + 3a2 = (4 - Ö3)a2 .



58.
Find integers a, b, c such that a ¹ 0 and the quadratic function f(x) = ax2 + bx + c satisfies


f(f(1)) = f(f(2)) = f(f(3)) .
Solution 1. Suppose that f(p) = f(q) with p ¹ q. Then a(p2 - q2) + b(p - q) = 0, from which p + q = -b/a. It follows from this (Explain!) that f(x) can take the same value at at most two distinct points. In particular, it is not possible that f(1) = f(2) = f(3). Nor can f(1), f(2), f(3) take three different values. Therefore, two of these take one value and the third a second value.

We make another preliminary observation. Suppose f(p) = f(q) = u, f(r) = v and f(u) = f(v), where p, q, r are different, and also u and v are different. Then, from the first paragraph, we have that p + q = u + v = -b/a.

Suppose, now, that (p, q, r) = (1, 2, 3) and that f(1) = u. Then


a + b + c
= u
4a + 2b + c
= u
9a + 3b + c
= 3 - u
so that 2(5a + 2b + c) = f(1) + f(3) = 3, which is not possible, since a, b and c are integers.

Suppose that (p, q, r) = (2, 3, 1). Then we are led to 2(5a + 2b + c) = 5, again an impossibility.

Suppose that (p, q, r) = (1, 3, 2) and that f(1) = u. Then


a + b + c
= u
9a + 3b + c
= u
4a + 2b + c
= 4 - u
so that 4a + b = 0 and 5a + b = 2u - 4. This leads to the assignment


(a, b, c) = (2u - 4, -8u + 16, 7u - 12)
so that


f(x)
= (2u - 4)(x2 - 4x) + (7u - 12)
= (2u - 4)(x - 2)2 - (u - 4)
= (2u - 4)(x - 1)(x - 3) + u  .
It can be checked that f(u) and f(4 - u) are equal to 2u3 - 12u2 + 23u - 12.

We can get a particular example by taking u = 0 to obtain the polynomial f(x) = -4(x - 1)(x - 3), in which case f(1) = f(3) = 0, f(2) = 4 and f(0) = f(4) = -12.

Solution 2. Let f(x) = ax2 + bx + c. Then f(1) = a + b + c, f(2) = 4a + 2b + c and f(3) = 9a + 3b + c. Then


f(f(2)) - f(f(1))
= a[(4a + 2b + c)2 - (a + b + c)2] + b[(4a + 2b + c) - (a + b + c)]
= (3a+b)[a(5a + 3b + 2c) + b]
= (3a + b)(5a2 + 3ab + 2ac + b)


f(f(3)) - f(f(1))
= a[(9a + 3b + c)2 - (a + b + c)2]+ b[(9a + 3b + c) - (a + b + c)]
= (8a + 2b)[a(10a + 4b + 2c) + b]
= 2(4a + b)(10a2 + 4ab + 2ac + b)
Suppose that f(f(1)) = f(f(2)) = f(f(3)). If b = -3a, then we must have 0 = 10a2 + 4ab + 2ac + b = 10a2 - 12a2 + 2ac - 3a, whence c = a + (3/2). In this case, a and c cannot both be integers. However, if b = -4a, then 0 = 5a2 + 3ab + 2ac + b = 5a2 - 12a2 + 2ac - 4a, whence c = (7a/2) + 2. So we can get integer coefficients by taking (a, b, c) = (2t, -8t, 7t + 2) for some integer t.

Comment. To get a single solution quickly, just try to make f(1) = f(3) = 1 and f(2) = 3. This leads immediately to f(x) = -(x - 2)2 + 3 = -2x2 + 8x - 5.



59.
Let ABCD be a concyclic quadrilateral. Prove that


|AC - BD | £ |AB - CD | .
Solution 1. [O. Bormashenko, P. Cheng] Let the diagonals intersect in M and assign the lengths: AB = a, BC = b, CD = c, DA = d, AM = r. BM = p, CM = s, DM = q. Since ÐABD = ÐACD and ÐBAC = ÐBDC, triangles MDC and MAB are similar, so that, for some k, q = kr, s = kp, c = ka. Wolog, we may assume that k ³ 1. Note that in triangle MAB, we have that p < r + a and r < p + a, whence -a < p - r < a or |p - r | < a.


|AC - BD |
= |(r + s) - (p + q) | = (k - 1)|p - r |
£ (k - 1)a = |c - a | = |AB - CD | .

Solution 2. Let the diagonals intersect in M and assign the lengths: AB = a, BC = b, CD = c, DA = d, AM = r. BM = p, CM = s, DM = q. Let ÐBAC = ÐBDC = b, ÐABD = ÐACD = d and ÐAMB = ÐDMC = f.

Applying the Law of Sines, we find that


p = a sinb
sinf
        q = c sind
sinf


r = asind
sinf
        s = c sinb
sinf
 .
Hence


p - r = a(sinb- sind)
sinf
         q - s = c(sind- sinb)
sinf
whence


(p + q) - (r + s)
= (a - c)(sinb- sind)
sinf
= (a - c)2cos((b+ d)/2)sin((b- d)/2)
sin(b+ d)
= (a - c)sin((b- d)/2)
sin((b+ d)/2)
 .
Since (b+ d)/2 £ 90°, the absolute value of the sine in the numerator is less than the sine in the denominator, and so we find that


|(p + q) - (r + s) | £ |a - c| ,
as desired.

Solution 3. [R. Furmaniak] Let O be the circumcentre of ABCD with R the circumradius. Let ÐAOB = a, ÐBOC = b, ÐCOD = g and ÐDOA = d. Wolog, we can let d be the largest of these angles.

We have that


AB = 2Rsin a
2
        CD = 2Rsin g
2


AC = 2R sin a+ b
2
     BD = 2Rsin b+ g
2
 .
Thus


AB - CD
= 2R æ
ç
è
sin a
2
- sin g
2
ö
÷
ø
= 4R sin a- g
4
cos a+ g
4
and


AC - BD = 4R sin a- g
4
cos a+ g+ 2b
4
 .
Since (a+ 2b+ g)/4 and (a+ g)/4 both do not exceed (a+ b+ g+ d)/4 = 90°, we have that


cos a+ g+ 2b
4
£ cos a+ g
4
 ,
and this yields the desired result.



60.
Let n ³ 2 be an integer and M = { 1, 2, ¼, n }. For every integer k with 1 £ k £ n, let


xk = å
{ min A + max A :A Í M, A  has  k  elements }
where min A is the smallest and max A is the largest number in A. Determine åk=1n (-1)k-1 xk.
Solution 1. For any set S = { a1, a2, ¼, ak } we define the related set S¢ = { (n+1) - ak, (n + 1) -ak-1 , ¼, (n + 1) - a1 }. As S runs through all the subsets of { 1, 2, ¼, n } with k elements, S¢ also runs through the same class of subsets; the mapping S ® S¢ is one-one. If, say, a1 is the minimum element and ak the maximum element of S, then (n+1)-a1 is the maximum and (n + 1) - ak the minimum element of S¢. Hence the sum of the minima and maxima of the two sets is


(a1 + ak) + 2(n+1) - a1 - ak = 2(n+1) .
The sum of the maxima and minima of all the sets SÈS¢ is equal to 2xk = 2(n+1)(n || k), so that xk = (n+1)(n || k). Hence


n
å
k=1 
(-1)k-1 xk = -(n+1) n
å
k=1 
(-1)k æ
ç
è
n
k
ö
÷
ø
= -(n + 1)[(1 - 1)n - 1] = n + 1 .

Solution 2. [R. Furmaniak] For a given k and m with 1 £ k, m £ n, the number of k-subsets of M with m as the smallest element is ((n-m) || (k-1)), and the number of k-subsets of M with m as the largest element is ((m-1) || (k-1)), We use the convention that (0 || 0) = 1 and (x || y) = 0 when x < y. >From this, we see that


xk
= é
ê
ë
n-k+1
å
m=1 
m æ
ç
è
n-m
k-1
ö
÷
ø
ù
ú
û
+ é
ê
ë
n
å
m=k 
m æ
ç
è
m-1
k-1
ö
÷
ø
ù
ú
û
= é
ê
ë
n
å
m=1 
m æ
ç
è
æ
ç
è
n-m
k-1
ö
÷
ø
+ æ
ç
è
m-1
k-1
ö
÷
ø
ö
÷
ø
ù
ú
û
 .
Hence


n
å
k=1 
(-1)k-1xk
= n
å
m=1 
é
ê
ë
m n
å
k=1 
(-1)k-1 æ
ç
è
n-m
k-1
ö
÷
ø
ù
ú
û
+ n
å
m=1 
é
ê
ë
m n
å
k=1 
(-1)k-1 æ
ç
è
m-1
k-1
ö
÷
ø
ù
ú
û
 .
= é
ê
ë
n-1
å
m=1 
m n
å
k=1 
(-1)k-1 æ
ç
è
n-m
k-1
ö
÷
ø
ù
ú
û
+ n æ
ç
è
0
0
ö
÷
ø
+ é
ê
ë
n-1
å
m=2 
m n
å
k=1 
æ
ç
è
m-1
k-1
ö
÷
ø
ù
ú
û
+ 1 æ
ç
è
0
0
ö
÷
ø
 .
Now, when n-m ³ 1,


n
å
k=1 
(-1)k-1 æ
ç
è
n-m
k-1
ö
÷
ø
= (1 - 1)n-m = 0
and, when m ³ 2,


n
å
k=1 
(-1)k-1 æ
ç
è
m-1
k-1
ö
÷
ø
= (1 - 1)m-1 = 0 .
It follows that the required sum is equal to n+1.

Solution 3. [O. Bormashenko] Denote by s the quantity åk=1n (-1)k-1xk. Let m be a number between 1 and n-1, inclusive. m is the minimum of a k-set for exactly ((n-m) || (k-1)) sets. For a particular k, m as minimum contributes n ((n-m) || (k-1)) to the sum for xk. Fixing m, m as minimum contributes to s the value


m n
å
k=1 
(-1)k-1 æ
ç
è
n-m
k-1
ö
÷
ø
= 0 ,
where (i || j) = 0 when j > i. The only other possible minimum is n, and this is a minimum only for the singelton { n }, so that n as minimum contributes n to the sum s.

By a similar argument, for any number m = 2, 3, ¼,n, m as maximum contributes 0 to the sum s. 1 is maximum only for the singleton { 1 } and contributes the value 1 to the sum s. Hence s = n + 1.