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
x_{1}, x_{2}, ¼, x_{n} be integers for which
x_{1}^{2} + x_{2}^{2} + ¼+ x_{n}^{2} + n^{3} £ (2n1)(x_{1} + x_{2} + ¼+ x_{n}) + n^{2} . 

Show that


(a) x_{1}, x_{2}, ¼, x_{n} are all nonnegative;


(b) x_{1} + x_{2} + ¼+ x_{n} + n + 1 is not
a perfect square.
Solution 1. The inequality can be rewritten as

n å
i=1

(x_{i}  n) (x_{i}  
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 x
_{i} is equal to either n or n
1. Therefore,
n^{2} + 1 = n(n1) + n + 1 £ x_{1} + x_{2} + ¼+ x_{n} + n + 1 £ n^{2} + 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

[2x_{k}  (2n1)]^{2} £ n . 

Since each term in the sum is odd, it can only be 1.
Therefore 2x
_{k}  (2n
1) =
±1, whence
x
_{k} 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

x_{i}(x_{i}  
2n1

) £ n^{2}  n^{3} . 

Observe that, for each i,
x_{i}( 
2n1

 x_{i}) £ [ 
1 2

(2n  1)]^{2} = n^{2}  n + 
1 4

. 

This is a consequence of the arithmeticgeometric means
inequality when the left side is positive, and obvious when
the left side is negative. Since x
_{i} is supposed to
be an integer, we must have
x_{i}( 
2n1

 x_{i}) £ n^{2}  n 

and equality occurs if and only if x
_{i} = n or
x
_{i} = 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
x_{i}(x_{i}  
2n1

) ³ n  n^{2} 

whence

n å
i=1

x_{i}(x_{i}  
2n1

) ³ n^{2}  n^{3} ,. 

with equality if and only if each x
_{i} 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  x_{i})^{2} £ 
n å
i=1

(n  x_{i}) . 
 (1) 
However, since x
_{i} is an integer for each i,
(n
 x
_{i})
^{2} ³ (n
 x
_{i}) with equality if and only if
n
 x
_{i} is equal to 0 or 1. Thus

n å
i=1

(n  x_{i})^{2} ³ 
n å
i=1

(n  x_{i}) 
 (2) 
with equality if and only if n
 x
_{i} = 0 or 1 for each i.
But (1) and (2) together imply that equality
does
occur for each i, whence x
_{i} 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}/_{2}AB 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 tan
q = (sin2
q)/(1 + cos2
q)
^{1}
or tan
q = tan(3
q 2
q) 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, 3a
^{2} = 4b
^{2}.
Since ÐDAC = ÐADB = 60^{°} and
ÐDAE = 15^{°}, it follows that
ÐEAC = 45^{°}.
We can determine EC  using the law
of cosines in DDEC. Thus,

= 4b^{2} + 4(a  b)^{2}  8(a  b)bÖ3/2 
 
= 8b^{2}  8ab + 4a^{2}  4abÖ3 + 4b^{2}Ö3 
 
= 4b^{2}(2 + Ö3)  4ab(2 + Ö3) + 4a^{2} 
 
= 3a^{2}(2 + Ö3)  2a^{2}Ö3(2 + Ö3)+ 4a^{2} 
 


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} = a^{2}  2ab + 4b^{2} = a^{2}  Ö3a^{2} + 3a^{2} = (4  Ö3)a^{2} . 


58.

Find integers a, b, c such that
a ¹ 0 and the
quadratic function f(x) = ax^{2} + 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(p
^{2}  q
^{2}) + 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)(x^{2}  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 2u
^{3}  12u
^{2} + 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) = ax^{2} + 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)(5a^{2} + 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)(10a^{2} + 4ab + 2ac + b) 


Suppose that f(f(1)) = f(f(2)) = f(f(3)).
If b =
3a, then we must have
0 = 10a
^{2} + 4ab + 2ac + b = 10a
^{2}  12a
^{2} + 2ac
 3a, whence c = a + (3/2). In this case,
a and c cannot both be integers.
However, if b =
4a, then
0 = 5a
^{2} + 3ab + 2ac + b = 5a
^{2}  12a
^{2} + 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 = 2x^{2} + 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+ 2
b+
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
x_{k} = 
å
 { 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=1}^{n} (1)^{k1} x_{k}.
Solution 1. For any set S = { a
_{1}, a
_{2},
¼, a
_{k} }
we define the related set S
¢ = { (n+1)
 a
_{k}, (n + 1)
a
_{k1} ,
¼, (n + 1)
 a
_{1} }. 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 oneone. If, say,
a
_{1} is the minimum element and a
_{k} the maximum element
of S, then (n+1)
a
_{1} is the maximum and (n + 1)
 a
_{k}
the minimum element of S
¢. Hence the sum of the
minima and maxima of the two sets is
(a_{1} + a_{k}) + 2(n+1)  a_{1}  a_{k} = 2(n+1) . 

The sum of the maxima and minima of all the sets S
ÈS
¢ is equal to
2x
_{k} = 2(n+1)(n  k), so that x
_{k} = (n+1)(n  k).
Hence

n å
k=1

(1)^{k1} x_{k} = (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 ksubsets of
M with m as the smallest element is ((nm)  (k1)),
and the number of ksubsets of M with m as the largest
element is ((m1)  (k1)), We use the convention that
(0  0) = 1 and (x  y) = 0 when x < y.
>From this, we see that

= 
é ê
ë


nk+1 å
m=1

m 
æ ç
è

nm
k1

ö ÷
ø


ù ú
û

+ 
é ê
ë


n å
m=k

m 
æ ç
è

m1
k1

ö ÷
ø


ù ú
û


 
= 
é ê
ë


n å
m=1

m 
æ ç
è


æ ç
è

nm
k1

ö ÷
ø

+ 
æ ç
è

m1
k1

ö ÷
ø


ö ÷
ø


ù ú
û

. 


Hence

= 
n å
m=1


é ê
ë

m 
n å
k=1

(1)^{k1} 
æ ç
è

nm
k1

ö ÷
ø


ù ú
û

+ 
n å
m=1


é ê
ë

m 
n å
k=1

(1)^{k1} 
æ ç
è

m1
k1

ö ÷
ø


ù ú
û

. 
 
= 
é ê
ë


n1 å
m=1

m 
n å
k=1

(1)^{k1} 
æ ç
è

nm
k1

ö ÷
ø


ù ú
û

+ n 
æ ç
è

0
0

ö ÷
ø

+ 
é ê
ë


n1 å
m=2

m 
n å
k=1


æ ç
è

m1
k1

ö ÷
ø


ù ú
û

+ 1 
æ ç
è

0
0

ö ÷
ø

. 


Now, when n
m
³ 1,

n å
k=1

(1)^{k1} 
æ ç
è

nm
k1

ö ÷
ø

= (1  1)^{nm} = 0 

and, when m
³ 2,

n å
k=1

(1)^{k1} 
æ ç
è

m1
k1

ö ÷
ø

= (1  1)^{m1} = 0 . 

It follows that the required sum is equal to n+1.
Solution 3. [O. Bormashenko] Denote by s
the quantity å_{k=1}^{n} (1)^{k1}x_{k}. Let m be a number
between 1 and n1, inclusive. m is the minimum of
a kset for exactly ((nm)  (k1)) sets.
For a particular k, m as minimum contributes
n ((nm)  (k1)) to the sum for x_{k}.
Fixing m, m as minimum contributes to s
the value
m 
n å
k=1

(1)^{k1} 
æ ç
è

nm
k1

ö ÷
ø

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