Let n be a positive integer. In a round-robin match, n teams compete and each pair of teams plays exactly one game. At the end of the match, the ith team has xi wins and yi losses. There are no ties. Prove that

x1 2 + x2 2 ++ xn 2 = y1 2 + y2 2 ++ yn 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 xi = yi . For each team, the total number of its wins and losses is equal to the number of games it plays. Thus xi + yi =n-1 for each i. Accordingly,

0=(n-1) i=1 n( xi - yi )= i=1 n( xi + yi )( xi - yi )= i=1 n( xi 2 - yi 2 )

from which the desired result follows.
Solution 2. Since xi + yi =n-1 for each i and x1 + x2 ++ xn = y1 + y2 ++ yn =( n 2 ) (the number of games played), we find that

i=1 n xi 2 = i=1 n[(n-1)- yi ]2 = i=1 n yi 2 -2(n-1) i=1 n yi + i=1 n(n-1)2 = i=1 n yi 2 -n(n-1)2 -n(n-1)2 = i=1 n yi 2 .

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= 12 + 12 + 12 + 12 + 12 + 12

12= 22 + 22 + 12 + 12 + 12 + 12

14= 33 + 12 + 12 + 12 + 12 + 12 .

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 ( t1 , t2 ,, tn-1 , tn ) be an n-tple of distinct integers, and suppose that the smallest of these is tn . Define t0 = tn , and wolog suppose that t0 = tn =0. Suppose that, for 1in, si = ti - ti-1 . Let the largest integer be tr ; since the integers are distinct, we must have

n-1 tr = tr - t0 = tr - t0 t1 - t0 ++ tr - tr-1 = s1 + s2 ++ sr


n-1 tr - t0 = tn - tr tr+1 - tr ++ tn - tn-1 = sr+1 ++ sn .


s1 + s2 ++ sn 2n-2.

By the root-mean-square, arithmetic mean (RMS-AM) inequality, we have that

( s1 2 + s2 2 ++ sn 2 n )1/2 s1 + s2 ++ sn n 2n-2 n ,

so that

s1 2 + s2 2 ++ sn 2 4 n2 -8n+4 n =4n-8+ 4 n .


i=1 n si 2 4n-8+4/n.

Since the sum of the differences of consecutive ti is zero, and so even, the sum of the squares is even. Since 4n-8 is even and n2, and since the sum exceeds 4n-8, we see that

i=1 n si 2 4n-8+2=4n-6.

How can this lower bound be achieved? Since it is equal to 22 (n-1)+ 12 + 12 , we can have n-2 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 6-tple (1,3,5,4,2,0).

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 arithmetic-geometric means inequality.
Solution 1. By the root-mean-square, 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 · 52

as desired.
Solution 2. By the RMS-AM inequality and the harmonic-arithmetic means inequality, we have that

a2 + b2 +(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+ 1 a )2 + (b+ 1 b )2 = a2 + b2 + a2 + b2 a2 b2 +4 =(a+b)2 -2ab+ (a+b)2 -2ab a2 b2 +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 Cauchy-Schwarz and arithmetic-geometric means inequalities, we find that

[ (a+ 1 a )2 + (b+ 1 b )2 ][ 12 + 12 ] = [ (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 [1+2+2]2 =25.

The desired result follows.

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/2x1, in which case all factors of the function are nonnegative. Then we can note, by the arithmetic-geometric means inequality, that

(1-x)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 -1x-1/2. For convenience, let u=-x, so that the want to maximize

(1+u)5 (1-u)(2u-1)2

for 1/2u1. In fact, we are going to maximize

[α(1+u)]5 [β(1-u)][γ(2u-1)]2

where α, β and γ are positive integers to be chosen to make 5α-β+4γ=0 (so that when we calculate the airthmetic mean of the eight factors, the coefficient of u will vanish), and α(1+u)=β(1-u)=γ(2u-1) (so that we can actually find a case where equality will occur). The latter conditions forces

β-α β+α = β+γ 2γ+β

or βγ=3αγ+2αβ. Plugging β=5α+4γ into this yields that

0=2(3αγ+5 α2 -2 γ2 )=2(5α-2γ)(α+γ).

Thus, let us take (α,β,γ)=(2,30,5). Then, by the arithmetic-geometric means inequality, we obtain that

[2(1+u)]5/8 [30(1-u)]1/8 [5(2u-1)]1/4 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 = 37 × 55 222 = ( 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,x0 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 37 × 55 × 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 37 × 55 × 2-22 occurs when x=-7/8.

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 ΔABC 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.

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 AMMR. 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 ΔARM 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.

Let a1 , a2 , , an be nonnegative integers such that, whenever 1i, 1j, i+jn, then

ai + aj ai+j ai + aj +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 ak =kx for 1kn.
(a) Solution. [R. Marinov] For positive integers n, let an =k-1 when n=2k and an =k when n=2k+1, so that the sequence is {0,1,1,2,2,3,3,}. Observe that

a(2p+1)+(2q+1) = a2(p+q+1) =p+q= a2p+1 + a2q+1

a2p+2q = a2(p+q) =p+q-1=(p-1)+(q-1)+1= a2p + a2q +1


a2p+(2q+1) = a2(p+q)+1 =p+q=(p-1)+q+1= a2p + a2q+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 semi-closed intervals [ ak /k, ak+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 aq /q( ap +1)/p. This is equivalent to paq qap +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) aq qap +q= qaq+r +q qaq + qar +q

whence raq qar +q and aq /q( ar +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+ pap + pas pap+s (p+s) ap +q= pap + sap +q

so that p+ pas sap +q> sap +p+s, pas sap +s and as /s( ap +1)/p, once again contradicting the minimality condition.