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
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
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,
|
|
|
= 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 |
| |
|
|
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
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
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
|
|
|
= (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
|
|
|
= 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) |
|
|
|
|
|
= 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.
|
|
|
= |(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
|
|
|
= |
(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
|
|
|
= 2R |
æ
ç
è
|
sin |
a
2
|
- sin |
g
2
|
|
ö
÷
ø
|
|
| |
|
|
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
|
|
|
= |
é
ê
ë
|
|
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
å
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.
