Solutions

171.

Let n be a positive integer. In a roundrobin
match, n teams compete and each pair of teams plays exactly
one game. At the end of the match, the ith team has
x_{i} wins and y_{i} losses. There are no ties. Prove that
x_{1}^{2} + x_{2}^{2} + ¼+ x_{n}^{2} = y_{1}^{2} + y_{2}^{2} + ¼+ y_{n}^{2} . 

Solution 1. Each game results in both a win and a loss,
so the total number of wins is equal to the total number of
losses. Thus
åx
_{i} =
åy
_{i}. For each team, the
total number of its wins and losses is equal to the number
of games it plays. Thus x
_{i} + y
_{i} = n
1 for each i.
Accordingly,
0 = (n1) 
n å
i=1

(x_{i}  y_{i}) = 
n å
i=1

(x_{i} + y_{i})(x_{i}  y_{i}) = 
n å
i=1

(x_{i}^{2}  y_{i}^{2}) 

from which the desired result follows.
Solution 2. Since x_{i} + y_{i} = n1 for each i
and x_{1} + x_{2} + ¼+ x_{n} = y_{1} + y_{2} + ¼+ y_{n} = (n  2) (the number of games played), we find that

= 
n å
i=1

[(n1)  y_{i}]^{2} 
 
= 
n å
i=1

y_{i}^{2} 2(n1) 
n å
i=1

y_{i} + 
n å
i=1

(n1)^{2} 
 
= 
n å
i=1

y_{i}^{2}  n(n1)^{2}  n(n1)^{2} = 
n å
i=1

y_{i}^{2} . 



172.

Let a, b, c, d. e, f be different
integers. Prove that
(a  b)^{2} + (b  c)^{2} + (c  d)^{2} + (d  e)^{2} + (e  f)^{2}+ (f  a)^{2} ³ 18 . 

Solution 1. Since the sum of the differences is 0, an even
number, there must be an even number of odd differences, and
therefore an even number of odd squares. If the sum of the
squares is less than 18, then this sum must be one of the
numbers 6, 8, 10, 12, 14, 16. The only possibilities for
expressing any of these numbers as the sum of six nonzero squares is
6 = 1^{2} + 1^{2} + 1^{2} + 1^{2} + 1^{2} + 1^{2} 

12 = 2^{2} + 2^{2} + 1^{2} + 1^{2} + 1^{2} + 1^{2} 

14 = 3^{3} + 1^{2} + 1^{2} + 1^{2} + 1^{2} + 1^{2} . 

Taking note that the sum of the differences is zero, the possible
sets of differences (up to order and sign) are
{ 1, 1, 1,
1,
1,
1 }, { 3, 1,
1,
1,
1,
1 },
{ 2, 2,
1,
1,
1,
1 }. Since the numbers are distinct,
the difference between the largest and smallest is
at least 5. This difference
must be the sum of differences between adjacent numbers; but checking
proves that in each case, an addition of adjacent differences must
be less than 5. Hence, it is not possible to achieve a sum of
squares less than 18. The sum 18 can be found with the set
{ 0, 1, 3, 5, 4, 2 }.
Solution 2. [A. Critch] We prove a more general result.
Let n be a positive integer exceeding 1.
Let (t_{1}, t_{2}, ¼, t_{n1}, t_{n})
be an ntple of distinct integers,
and suppose that the smallest of these is t_{n}. Define t_{0} = t_{n},
and wolog suppose that t_{0} = t_{n} = 0.
Suppose that, for 1 £ i £ n, s_{i} = t_{i}  t_{i1} .
Let the largest integer be
t_{r}; since the integers are distinct, we must have

£ t_{r} = t_{r}  t_{0} = t_{r}  t_{0}  
 
£ t_{1}  t_{0} + ¼+ t_{r}  t_{r1}  
 
= s_{1} + s_{2} + ¼+ s_{r} 


and

£ t_{r}  t_{0} = t_{n}  t_{r}  
 
£ t_{r+1}  t_{r} + ¼+ t_{n}  t_{n1}  = s_{r+1} + ¼+ s_{n} . 


Hence.
s_{1} + s_{2} + ¼+ s_{n} ³ 2n  2 . 

By the rootmeansquare, arithmetic mean (RMSAM)
inequality, we have that

æ ç
è


s_{1}^{2} + s_{2}^{2} + ¼+ s_{n}^{2} n


ö ÷
ø

1/2

³ 
s_{1} + s_{2} + ¼+ s_{n} n

³ 
2n  2 n

, 

so that
s_{1}^{2} + s_{2}^{2} + ¼+ s_{n}^{2} ³ 
4n^{2}  8n + 4 n

= 4n  8 + 
4 n

. 

Thus,

n å
i=1

s_{i}^{2} ³ 4n  8 + é4/n ù . 

Since the sum of the differences of consecutive t
_{i} is zero, and
so even, the sum of the squares is even. Since 4n
 8 is even
and n
³ 2, and since the sum exceeds 4n
 8, we see that

n å
i=1

s_{i}^{2} ³ 4n  8 + 2 = 4n  6 . 

How can this lower bound be achieved? Since it is equal to
2^{2} (n  1) + 1^{2} + 1^{2}, we can have n2 differences equal to
2 and 2 differences equal to 1. Thus, we can start by going up
the odd integers, and then come down via the even integers to 0.
In the case of n = 6, this yields the 6tple (1, 3, 5, 4, 2, 0).

173.

Suppose that a and b are positive real numbers
for which a + b = 1. Prove that

æ ç
è

a + 
1 a


ö ÷
ø

2

+ 
æ ç
è

b + 
1 b


ö ÷
ø

2

³ 
25 2

. 

Determine when equality holds.
Remark. Before starting, we note that when a + b = 1,
a, b > 0, then ab
£ ^{1}/
_{4}. This is an immediate consequence
of the arithmeticgeometric means inequality.
Solution 1. By the rootmeansquare, arithmetic mean inequality,
we have that

1 2


é ê
ë


æ ç
è

a + 
1 a


ö ÷
ø

2

+ 
æ ç
è

b + 
1 b


ö ÷
ø

2


ù ú
û



³ 
1 4


é ê
ë


æ ç
è

a + 
1 a


ö ÷
ø

+ 
æ ç
è

b + 
1 b


ö ÷
ø


ù ú
û

2


 
= 
1 4


æ ç
è

1 + 
1 a

+ 
1 b


ö ÷
ø

2

= 
1 4


æ ç
è

1 + 
1 ab


ö ÷
ø

2

³ 
1 4

·5^{2} 


as desired.
Solution 2. By the RMSAM inequality and the
harmonicarithmetic means inequality, we have that
a^{2} + b^{2} + (1/a)^{2} + (1/b)^{2} 

³ 
1 2

(a + b)^{2} + 
1 2


æ ç
è


1 a

+ 
1 b


ö ÷
ø

2


 
= 
1 2

+ 2 
é ê
ë


(1/a) + (1/b) 2


ù ú
û

2


 
³ 
1 2

+ 2 · 
4 (a+b)^{2}

= 
17 2

, 


from which the result follows.
Solution 3.

 
= a^{2} + b^{2} + 
a^{2} + b^{2} a^{2}b^{2}

+ 4 
 
= (a + b)^{2}  2ab + 
(a+b)^{2}  2ab a^{2}b^{2}

+ 4 
 
= 5  2ab + 
1 (ab)^{2}

 
2 ab


 
= 4  2ab + 
æ ç
è


1 ab

 1 
ö ÷
ø

2

³ 4  2 
æ ç
è


1 4


ö ÷
ø

+ (4  1)^{3} = 
25 2

. 


Solution 4. [F. Feng] From the CauchySchwarz and
arithmeticgeometric means inequalities, we find that

+ 
æ ç
è

b + 
1 b


ö ÷
ø

2


ù ú
û

[1^{2} + 1^{2}] 
 
= 
é ê
ë


æ ç
è

a + 
1 a


ö ÷
ø

2

+ 
æ ç
è

b + 
1 b


ö ÷
ø

2


ù ú
û

[(a + b)^{2} + (a + b)^{2} ] 
 
³ 
é ê
ë


æ ç
è

a + 
1 a


ö ÷
ø

(a + b) + 
æ ç
è

b + 
1 b


ö ÷
ø

(a + b) 
ù ú
û

2


 
= 
é ê
ë

(a + b)^{2} + 2 + 
æ ç
è


a b

+ 
b a


ö ÷
ø


ù ú
û

2


 


The desired result follows.

174.

For which real value of x is the function
(1  x)^{5} (1 + x)(1 + 2x)^{2} 

maximum? Determine its maximum value.
Solution 1. The function assumes negative values when
x <
1 and x > 1. Accordingly, we need only consider its
values on the interval [
1, 1]. Suppose, first, that
1/2
£ x
£ 1, in which case all factors of the function
are nonnegative. Then we can note, by the arithmeticgeometric
means inequality, that
(1x)^{5}(1+x)(1+2x) £ [(5/8)(1  x) + (1/8)(1 + x) + (2/8)(1 + 2x)]^{8} = 1 

with equality if and only if x = 0. Thus, on the interval [
1/2, 1],
the function takes its maximum value of 1 when x = 0.
We adopt the same strategy to consider the situation when
1 £ x £ 1/2. For convenience, let u = x, so that
the want to maximize
(1 + u)^{5} (1  u)(2u  1)^{2} 

for 1/2
£ u
£ 1. In fact, we are going to maximize
[a(1 + u)]^{5} [b(1  u)] [g(2u  1)]^{2} 

where
a,
b and
g are positive integers to be
chosen to make 5
a b+ 4
g = 0 (so that when we
calculate the airthmetic mean of the eight factors, the coefficient
of u will vanish), and
a(1 + u) =
b(1
 u) =
g(2u
 1) (so that we can actually find a case where equality will
occur). The latter conditions forces
or
bg = 3
ag+ 2
ab. Plugging
b = 5
a+ 4
g into this yields that
0 = 2(3ag+ 5a^{2}  2g^{2}) = 2(5a 2g)(a+ g) . 

Thus, let us take (
a,
b,
g) = (2, 30, 5).
Then, by the arithmeticgeometric means inequality, we obtain that
[2(1 + u)]^{5/8} [30(1  u)]^{1/8} 

 
£ 
5 4

(1 + u) + 
15 4

(1  u) + 
5 4

(2u  1) = 
15 4

, 


with equality if and only if 2(1 + u) = 30(1
 u) = 5(2u
 1),
i.e., u = 7/8. Hence,
(1  x)^{5} (1 + x)(1 + 2x)^{5} 

= (1 + u)^{5}(1  u)(1  2u)^{2} 
 
£ 
æ ç
è


15 8


ö ÷
ø

8

2^{5/8} 30^{1} 5^{2} 
 
= 
3^{7} ×5^{5} 2^{22}

= 
æ ç
è


15 16


ö ÷
ø

5


æ ç
è


9 4


ö ÷
ø

, 


with equality if and only if x =
7/8.
It remains to show whether the value of the function when x = 7/8
exceeds its value when x = 0. Recall the Bernoulli inequality:
(1 + x)^{n} > 1 + nx for 1 < x, x ¹ 0 and positive integer
n. This can be established by induction (do it!). Using this,
we find that

æ ç
è


15 16


ö ÷
ø

5


æ ç
è


9 4


ö ÷
ø

> 
æ ç
è

1  
5 16


ö ÷
ø

×2 = 
22 16

> 1 . 

Thus, the function assumes its maximum value of 3
^{7} ×5
^{5}×2
^{22} when x =
7/8.
Solution 2. Let f(x) = (1  x)^{5}(1 + x)(1 + 2x)^{2}.
Then f¢(x) = 2(1  x)^{4}(1 + 2x)x(7 + 8x). We see that
f¢(x) > 0 if and only if x < 7/8 or 1/2 < x < 0.
Hence f(x) has relative maxima only when x = 7/8 and
x = 0. Checking these two candidates tells us that the
absolute maximum of 3^{7} ×5^{5} ×2^{22} occurs when
x = 7/8.

175.

ABC is a triangle such that AB < AC. The point D
is the midpoint of the arc with endpoints B and C of that arc of
the circumcircle of DABC that contains A. The foot of the
perpendicular from D to AC is E. Prove that AB + AE = EC.
Solution 1. Draw a line through D parallel to AC that
intersects the circumcircle again at F. Let G be the foot
of the perpendicular from F to AC. Then DEGF is a rectangle.
Since arc BD is equal to arc DC, and since arc AD is equal to
arc FC (why?), arc BA is equal to arc DF. Therefore the
chords of these arcs are equal, so that AB = DF = EG.
Hence AB + AE = EG + GC = EC.
Solution 2. Note that the length of the shorter arc AD is
less than the length of the shorter arc DC. Locate a point H
on the chord AC so that AD = HD. Consider triangles
ABD and HCD. We have that AD = DH, BD = CD and
ÐABD = ÐHCD. This is a case of SSA congruence, the
ambiguous case. Since angles BAD and DHC are both obtuse (why?),
they must be equal rather the supplementary, and the triangles
ABD and HCD are congruent. (Congruence can also be established
using the Law of Sines.) In particular, AB = HC. Since
triangle ADH is isosceles, E is the midpoint of AH, so that
AB + AE = HC + EH = EC.
Solution 3. Let DM be a diameter of the circumcircle, so that
M is the midpoint of one of the arcs BC. Let H be that point on
the chord AC for which DA = DH and let DH be produced to meet
the circle again in K. Since ÐMAD = ÐDEA = 90^{°},
it follows that ÐMAC = 90^{°}  ÐEAD = ÐADE.
Since AM and DE are both angle bisectors, ÐBAC = ÐADH.
Because ADCK is concyclic, triangles ADH and KCH are similar,
so that HC = CK. From the equality of angles BAC and ACK,
we deduce the equality of the arcs BAC and ACK, and so the
equality of the arcs BA and CK. Hence AB = CK = HC.
Therefore AB + AE = HC + EH = EC.
Solution 4. [R. Shapiro] Since A lies on the short arc
BD, ÐBAD is obtuse. Hence the foot of the perpendicular
from D to BA produced is outside of the circumcircle of
triangle ABC. In triangles KBD and ECD,
ÐBKD = ÐDEC = 90^{°}, ÐKBD = ÐABD = ÐACD and BD = CD. Hence the triangles
KBD and ECD are congruent, so that DK = DE and BK = EC.
Since the triangle ADK and ADE are right with a common
hypotenuse AD and equal legs DK and DE, they are congruent
and AK = AE. Hence EC = BK = BA + AK = BA + AE, as desired.

176.

Three noncollinear points A, M and N are given in
the plane. Construct the square such that one of its vertices is
the point A, and the two sides which do not contain this vertex are
on the lines through M and N respectively. [Note: In such
a problem, your solution should consist of a description of the
construction (with straightedge and compasses) and a proof in
correct logical order proceeding from what is given to what is
desired that the construction is valid. You should deal with
the feasibility of the construction.]
Solution 1. Construction.
Draw the circle with diameter MN and centre O. This circle
must contain the point C, as MC and NC are to be perpendicular.
Let the right bisector of MN meet the circle in K and L.
Join AK and, if necessary, produce it to meet the circle at C.
Now draw the circle with diameter AC and let it meet the right
bisector of AC at B and D. Then ABCD is the required
rectangle. There are two options, depending how we label the
right bisector KL.
However, the construction does not work if A actually lies on the
circle with diameter MN. In this case, A and C would coincide
and the situation degenerates. If A lies on the right bisector of
MN, then C can be the other point where the right bisector
intersects the circle, and M and N can be the other two vertices
of the square. If A is not on the right bisector, then there
is no square; all of the points A, M, C, N would have to
be on the circle, and AM and AN would have to subtend angles
of 45^{°} at C, which is not possible.
Proof. If C and O are on the same side of KN, then
ÐKCN = ^{1}/_{2}ÐKON = 45^{°}, so that
CN makes an angle of 45^{°} with AC produced, and so
CN produced contains a side of the square. Similarly, CM produced
contains a side of the square. If C and O are on opposite sides
of KN, then ÐKCN = 135^{°}, and CN still makes an
angle of 45^{°} with AC produced; the argument can be
completed as before.
Solution 2. Construction. Construct circle of diameter
MN. Draw AM = MR (with the segment MR intersecting
the interior of the circle) and
AM ^MR. Construct the circle AMR.
Let this circle intersect the given circle at C. Then construct the
square with diagonal AC. If A lies on the circle, then the candidates
for C are A and M. We cannot take C = A, as the situation
degererates; if we take C = M, then the angle ACM and segment
CM degenerate. We can complete the analysis as in the first
solution.
Proof. Since DARM is right isosceles, ÐARM = 45^{°}. Hence the circle is the locus of points at which
AM subtends an angle equal to 45^{°} or 135^{°}.
Hence the lines AC and CM intersect at an angle of 45^{°}.
Since ÐMCN = 90^{°}, the lines AC and CN also
intersect at 45^{°}. It follows that the remaining points
on the square with diagonal AC must lie on the lines CM and
CN.

177.

Let a_{1}, a_{2}, ¼, a_{n} be nonnegative
integers such that, whenever 1 £ i, 1 £ j,
i + j £ n, then
a_{i} + a_{j} £ a_{i+j} £ a_{i} + a_{j} + 1 . 



(a) Give an example of such a sequence which is not
an arithmetic progression.


(b) Prove that there exists a real number x such that
a_{k} = ëkx û for 1 £ k £ n.
(a)
Solution. [R. Marinov] For positive integers n, let
a
_{n} = k
 1 when n = 2k and a
_{n} = k when n = 2k + 1, so
that the sequence is { 0, 1, 1, 2, 2, 3, 3,
¼}.
Observe that
a_{(2p+1)+(2q+1)} = a_{2(p+q+1)} = p + q = a_{2p+1} + a_{2q+1} 

a_{2p + 2q} = a_{2(p+q)} = p + q  1 = (p  1) + (q  1) + 1 = a_{2p} + a_{2q} + 1 

and
a_{2p + (2q + 1)} = a_{2(p + q) + 1} = p + q = (p  1) + q + 1 = a_{2p} + a_{2q + 1} 

for positive integers p and q, whence we see that this
sequence satisfies the condition. The corresponding value of x
is 1/2.
Solution. [A. Critch] The assertion to be proved is that
all the semiclosed intervals [a_{k}/k, a_{k+1}/k) have a point in
common. Suppose, if possible, that this fails. Then there must
be a pair (p, q) of necessarily distinct integers for which
a_{q}/q ³ (a_{p} + 1)/p. This is equivalent to
pa_{q} ³ qa_{p} + q. Suppose that the sum of these
two indices is as small as possible.
Suppose that p > q, so that p = q + r for some positive r.
Then
(q + r)a_{q} ³ qa_{p} + q = qa_{q+r} + q ³ qa_{q} + qa_{r} + q 

whence ra
_{q} ³ qa
_{r} + q and a
_{q}/q
³ (a
_{r} + 1)/r. Thus
p and r have the property of p and q and we get a contradiction
of the minimality condition.
Suppose that p < q, so that q = p + s for some positive s.
Then
p + pa_{p} + pa_{s} ³ pa_{p+s} ³ (p + s)a_{p} + q = pa_{p} + sa_{p} + q 

so that p + pa
_{s} ³ sa
_{p} + q > sa
_{p} + p + s, pa
_{s} ³ sa
_{p} + s
and a
_{s}/s
³ (a
_{p} + 1)/p, once again contradicting the minimality
condition.