Usa Mathematical Olympiads 1972-1986

XPREFACEThe Olympiad itself was to consist of five essay-type problems requiringmathematical power of the contestants and to be done in 3 hours (laterchanged to 3: hours). The purpose of the Olympiad was to discover andencourage secondary school students with superior mathematical talent,students who possessed mathematical creativity and inventiveness as well ascompetence in mathematical techniques. Also, the top eight contestantscould be selected as team members for subsequent participation in theIMO. Participation in the USAMO was to be by invitation only and limitedto about 100 students selected from the top of the Honor Roll on theAmerican High School Mathematics Examination (AHSME) plus possiblya few students of superior ability selected from those states that did notparticipate in the AHSME but had their own annual competitions. Theeligibility requirements are now different due to the introduction in 1983 ofan intermediate competition, the American Invitational Mathematics Examination (AIME) consisting of 15 problems of which only the numericalanswer is to be determined. These problems are more challenging thanthose in the AHSME (a multiple choice exam) but not than those in theUSAMO. All regularly enrolled secondary school students in the USA andCanada are eligible to write the AHSME, and the number who do so is onthe order of 400,OOO. Those students who obtain at least a mark of 100 (outof 150) are invited to write the AIME, and the number who do so is on theorder of 5,000. Those students who are then invited to write the USAMOare the 150 (approximately) who have the highest index score, the latterbeing the AHSME score plus 10 X the AIME score (max 15) so that each isequally weighted. The top 8 students in the USAMO are declared thewinners and are invited to Washington, D.C. to receive prizes. The finalwind up of the 3 competitions is an invited training session for 24 students(must be USA citizens or residents) to practise for the IMO competition.These consist of the top 8 students of the USAMO plus the few students, ifany, who have obtained honorable mention and have participated in aprevious IMO. The rest of the 24 places go to non-senior students at the topof the honor roll. If the 24 places have not been filled, then those non-seniorstudents with the top combined index score of AHSME 10 X AIME 4 x USAMO (max 100) are selected. The 6 (previously 8) students who areto be the IMO team members are selected on the basis of the USAMOscore plus the further tests at the training session.For further information on these competitions as well as the AmericanJunior High School Mathematics Examination (AJHSME), write to theExecutive Director of the American Mathematics Competitions, ProfessorWalter E. Mientka, Department of Mathematics and Statistics, Universityof Nebraska, Lincoln, Nebraska 68588-0322.The first USAMO Committee consisted of S. L. Greitzer, chairman, A.Kalfus, N. D. Turner and myself. Even though, according to my files, S. L.

PREFACExiGreitzer was initially doubtful about starting a USAMO, once it wasapproved, he became a very efficient one-man administrator of it for manyyears subsequently. I had set the problems and they were checked out by A.Schwartz and D. J. Newman. Invitations were sent to 106 students on April14, 1972, and 100 students took the First USA Olympiad on May 9,1972. The papers were graded by J. Bender, A. Bumby, S. Leader, B.Muckenhoupt, and H. Zimmerberg of Rutgers University. The top paperswere then regraded by L. M. Kelly of Michigan State University andmyself.The top eight contestants (their names and school affiliations as well asthose of subsequent winners are listed in the Appendix) were honored inJune 1972 in Washington D.C. at a prestigous three-part Awards Ceremony arranged very effectively by N. D. Turner (and for many yearssubsequently): the bestowing of awards and the giving of the OlympiadAddress by Emmanuel R. Piore in the Board Room of the NationalAcademy of Sciences, and the reception and dinner in the rooms of theDiplomatic Reception Area of the Department of State. The costs of theseceremonies were defrayed by a generous grant from the IBM Corporation.These ceremonies were repeated in successive years (with several exceptionswhen the reception and dinner were held in the Great Hall of the NationalAcademy of Science) and defrayed by continued generous grants from IBMand MAA support. Some of the successive addresses were given bySaunders MacLane, Lowell J. Paige, Peter D. Lax, Andrew M. Gleason,Alan J. Hoffman, Ivan Niven, Charles Fefferman, Ronald L. Graham, andNeil J. Sloane.During 1973-1985, the problems in the USAMO were set by an Examination Subcommittee consisting of three members (increased to four after1982) of which I was chairman. Peter Paige, Cecil C. Rousseau, TomGriffiths, Andy Liu, and Joseph Konhauser have served on this subcommittee during this 12 year period; I am pleased to acknowledge their long timecollaboration. After my resignation from the committee, Ian Richardsbecame the new chairman.The solutions of the USAMO problems have been compiled annuallyfrom the solutions of the Examination Committee and made available inpamphlet form for a nominal charge. This compilation was first done byS. L. Greitzer up through 1982, by A. Liu and myself during 1983-5, andby C. C. Rousseau in 1986. Naturally, many of the solutions in this bookare similar to those previously published. Moreover, the solutions have beenedited, quite a number have been changed and/or extended, and referenceshave been added where pertinent. Although the problems are arranged inchronological order at the beginning, the solutions are arranged by subjectmatter to facilitate the learning in a particular field. The subject matterclassifications are Algebra, Number Theory, Plane Geometry, Solid Geome-

xiiPREFACEtry, Geometric Inequalities, Inequalities, and Combinatorics & Probability.A previous example of this type of arrangement occurs in the recommendedbook [48]. Also, at the end is a Glossary of some frequently used terms andtheorems as well as a comprehensive bibliography with items numbered andreferred to in brackets in the text.The solutions given here are more detailed than need be for the USAMOcontestants, since it was the consensus of the NML Committee that thiswould make them more accessible and of service to a wider audience.A frequent concern of contestants is how detailed a solution has to be toobtain full marks. This of course depends on the graders. One should avoid“hand waving” arguments and when in doubt, one should include detailsrather then leave them out. It is in this aspect that Olympiad type competitions are vastly superior to the AJHSME, AHSME, and AIME typecompetitions. In the former type, one has to give a well written completesustained argument to obtain full marks whereas in the AJHSME and theAHSME one can just guess at the correct multiple choice answers, and inthe AIME one does not have to substantiate any of the numerical answers.This ability to write is very important and is only recently being emphasized. I and many others do not care for multiple choice type competitionsor even those like the AIME. Apparently, the raison d’ttre for these typesof competitions is the relative ease of administering them to the very largenumber of contestants. This could be achieved by having run off competitions graded locally and only the final competition with a small number ofcontestants graded centrally. In the European socialist countries, wherethere is a strong tradition in mathematical competitions, there are separateOlympiads for the 7th, 8th, 9th, and 10th grades. It is very unfortunate thatwe do not have at the very least a junior Olympiad type competition as afollow up for the AJHSME.In the grading of the USAMO there are extra marks for elegant solutionsand/or non-trivial generalizations with proof. Although generalizations arepart and parcel of mathematical creativity and elegant solutions are muchmore satisfactory and transparent than non-elegant ones, finding themusually takes extra time, unless one has some special a priori knowledge, orelse one has had long practise in finding them. So contestants should not“go too far out of their way” looking for elegance or generalizations.Nevertheless, if there is time, contestants are advised to strive for refinements, since elegance is frequently a sign of real understanding andgeneralization a sign of creativity.No doubt, many of the solutions given here can be improved upon orgeneralized, particularly with special a priori knowledge; when a readerfinds this to be the case, I would be very grateful to receive any suchcommunications.

PREFACE.XlllI am greatly indebted to the late Samuel L. Greitzer and to Andy Liu forsharing the joys and burdens of the USAMO Committee as well as the joysand burdens of coaching the USA Olympiad teams and participating in theIMO from 1975-1980 and 1981-1984, respectively, and also to Walter E.Mientka, Executive Director of the American Mathematics Competitions,for his continued cheerful efficient cooperation over many years. I am alsograteful to the Examination Committee members mentioned previously,Samuel L. Greitzer, Peter D. Lax, Andy Liu, Peter Ungar and all membersof the NML Committee, particularly Anneli Lax and Ivan Niven forimprovements and additions. Lastly but not least, I am very grateful to mywife Irene for her assistance with this book in many ways.Murray S. KlamkinUniversity of Alberta

ContentsPrefaceUSA Olympiad ProblemsSolutions of Olympiad ProblemsAlgebra (A)Number Theory (N.T.)Plane Geometry (P.G.)Solid Geometry (S.G.)Geometric Inequalities (G.I.)Inequalities (I)Combinatorics & Probability (C.& P.)ix11515304555668193Appendix105List of Symbols110Glossary111References120

List of Symbolsarea of A ABCapproximately equal tocongruent (in geometry)a - b is divisible by p ; Congruence. see Glossarya - b is not divisible by pidentically equal tointeger part of x. i.e. greatest integer not exceedingXleast integer greater than or equal to xbinomial coefficient. see Glossary; also thenumber of combinations of n things. k at a timethe greatest common divisor of n and kp divides np does not divide nn factorial 1 . 2 . 3 . . . . ( n - 1 ) n . O! 1the product a , . a , . . . . .a,,similar in geometrythe sum a,f g( x ) a, . . . a, f[g( x)],see Composition in Glossaryunion of sets K,. K ,intersection of sets K,. K ,arithmetic mean, see Mean in Glossarygeometric mean, see Mean in Glossaryharmonic mean, see Mean in Glossaryclosed interval, i.e. all x such that a x hopen interval, i.e. all x such that a .Y h0

GLOSSARY111Glossary of some frequently used terms and theorems.Arithmetic mean (average). see MeanArithmetic mean-geometric mean inequality ( A . M . 4 . M. inequalit?.).If a,, a 2 , ., a , are n non-negative numbers, then1"n1-1with equality if and only ifa, a, . a,,.Weighted arithmetic mean-geometric mean inequality.If. in addition, w1, w 2 , . . . , w , are non-negative numbers (weights)whose sum is 1. thennnr-1w,a, 2n1I-a:,with equality if and only ifa, a2 - an.For a proof, use Jensen's inequality below, applied to f ( x ) - log x.Arithmetic Series. see SeriesBinomial coefficient.(i) n!k!(n- k)!n lAlso( ) (bols.) ( If k ) coefficient of y k in the expansion ( 1) ( i ) (See. Binomial theorem and List of Sym )')'IBinomial theorem.(x y)"( i ) x " - " y k , where k-0n ( n - 1) . . . ( n - k 1)-n!k!(n- k ) !'

U S A MATHEMATICAL O L Y M P I A D S112Cauchy ‘s inequality.For vectors x,y, (x yI G Ixlbl;x l , y l , i 1,2 ,., n ,-componentwise, for real numbersThere is equality if and only if x,y are collinear, i.e., if and only ifx, ky,, i 1,2, .,n. A proof for vectors follows from the definition of dot product x y Ixl&lcos(x,y) or by considering the discriminant of the quadratic function q ( t ) C(y,t - x,),.Centroid of a triangle.Point of intersection of the mediansCeva ’s theorem.If AD, BE, CF are concurrent cevians of a triangle ABC, then6)BD * CE . AF DC . EA * FB.Conversely, if AD, BE,CF are three cevians of a triangle ABC suchthat (i) holds, then the three cevians are concurrent. (A cevian is asegment joining a vertex of a triangle with a point on the oppositeside.)Chinese remainder theorem.Let m l , m,,. ., m , denote n positive integers that are relativelyprime in pairs, and let al, a,, . ., a,, denote any n integers. Then thecongruences x a,(mod M I ) , i 1,2,. . , n have common solutions;any two solutions are congruent modulo m l m 2 . . m,,. For a proof, see[112, p. 311.Circumcenter of A ABC.Center of circumscribed circle of A ABCCircumcircle of A ABC.Circumscribed circle of A ABCComplex numbers.Numbers of the form x iy, wherex, y are real and i q.Composition of functions.F( x ) f 0 g( x ) f[g( x)] is the composite of functions, f, g, wherethe range of g is the domain of f.Congruence.a 2 b(modp) read “a is congruent to b modulo p” means that a - bis divisible by p .Concave function.f( x ) is concave if -f( x ) is convex; see Convex function.

GLOSSARY113Convex function.A function f ( x ) is convex in an interval I if for all x,, x 2 in I andfor all non-negative weights w,. w 2 with sum 1.Wlf(X1) wzf(x2)2/(w,x, WZX,).Geometrically this means that the graph of f between (xl. f ( x l ) )and ( x , , f ( x 2 ) )lies below its secants.We state the following useful facts:1. A continuous function which satisfies the above inequality forw w 1/2 is convex.2. A twice differentiable function f is convex if and only if f " ( x ) isnon-negative in the interval in question.3. The graph of a differentiable convex function lies above its tangents.For an even more useful fact, see Jensen's inequality.,Convex hull oj a pointset S.The intersection of all convex sets containing SConvex pointset.A pointset S is convex if, for every pair of points P, Q in S, all pointsof the segment PQ are in S.Cross product (vector product) xXy of W Gvectors.see Vectors.Cyclic pohgon .Polygon that can be inscribed in a circle.de Moivre 's theorem.(cos 8 i sin 8)" cos n8 i sin n8. For a proof, see N M L vol. 27, p.49.Determinant of a square matrix M (det M ) .A multi-linear function f ( C , , C,, . . . , C,,) of the columns of M withthe propertiesf( c,,c,,. . ., c,,. . . , c,,. . . , C") -f( c,,c,. . . . ,c,, . . . , c,,. . ., C")and det I 1. Geometrically, det(C,, C,, . . . ,C,) is the signed volumeof the n-dimensional oriented parallelepiped with coterminal sidevectors C,,C,. . . C,.Dirichlet 's principle. see Pigeonhole principle.Dot product (scalar product) x . y of two vectors. see Vectors.Escribed circle. see Excircle.Euclid 's algorithm.A process of repeated divisions yielding the greatest common divisor oftwo integers, m n:

U S A MATHEMATICAL OLYMPIADS114m nq, r l . 91 r1q2 r2. ., qr rh9r l r h , :the last non-zero remainder is the GCD of m and n. For a detaileddiscussion. see e.g. C. D. Olds, Continued Fractions, N M L vol. 9(1963). p. 16.Euler 's extension of Fermat 's theorem. see Fermat 's theorem.Euler 's theorem on the distance d between in- and circumcenters of a triangle.d dm , where r. R are the radii of the inscribed and circumscribed circles.Excircle of A A BC.A circle that touches one side of the triangle internally and the othertwo (extended) externally.Fermat 's Theorem.If p is a prime, ap a(mod p ) .Euler 's extension of - .If m is relatively prime to n , then me'") l(mod n ) , where theEuler @ ( n ) function is defined to be the number of positive integersIn and relatively prime to n. There is a simple formula for @:i 3@ ( n ) n n 1 - - , where p, are distinct prime factors of nFundamental summation formula.Our name for the telescoping sum formula, to point out its similarity tothe Fundamental Theorem of Calculus. see Summation of Series.Geometric mean. see Mean, geometric.Geometric series. see Series, geometric.Harmonic mean. see Mean, harmonic.Heron's formula.The area of AABC with sides a , b, c is[ A B C ] /s(s - a ) ( s - b ) ( s - c ) , where s :(a h c).Holder's inequulity.If u,, h, are non-negative numbers, and if p . q are positive numberssuch that ( l / p ) ( l / q ) 1, thenu,h, a,h, . . . u,,h,, ( u : u i . . . u!')l''(hy hy . . . h:)""with equality if and only if a , kb,, i 1.2,. ., n. Cauchy's inequality corresponds to the special case p 9 2.

GLOSSARY115Homogeneous.f(x, .v, z . . . . ) is homogeneous of degree k iff( tx. t.v,tz. .) r k j ( x , s, z , . . . ).A system of linear equations is called homogeneous if each equation isof the form f( x, .v. z . . . . ) 0 with f homogeneous of degree 1.Homothets.A dilatation (simple stretch or compression) of the plane (or space)which multiplies all distances from a fixed point. called the center ofhomothety (or similitude), by the same factor X # 0. This mapping(transformation) is a similarity which transforms each line into aparallel line, and the only point unchanged (invariant) is the center.Conversely. if any two similar figures have their corresponding sidesparallel. then there is a homothety which transforms one of them intothe other, and the center of homothety is the point of concurrence ofall lines joining pairs of corresponding points. Two physical examplesare a photo enlarger and a pantograph.Incenter of A A BC.Center of inscribed circle ofIncircle of A A BC.Inscribed circle ofA A BCA ABCInequalities.A. M. - G . M.-see Arithmetic meanA.M. - H.M.-see Mean. HarmonicCauch.v- see Cauch?,'sH.M. - G . M.-see Mean. HarmonicHolder-see Holder 'sJensen- see Jensen'sPower mean -see Power meanSchur-see Schur 'sTriangle- see TriangleInverse function.f: X Y has an inverse f-' if for everv y in the range of f thereis a unique x in the domain of f such that f ( x ) ?*; then f '(.v) x. and f-' 0 f. f f-' are the identity functions. See also Composition.0Irreducible poivnomial.A polynomial g(x), not identically zero, is irreducible over a field Fif there is no factoring, g ( x ) r ( x ) s ( x ) , of g ( x ) into two polynomials r ( x ) and s ( x ) of positive degrees over F. For example. x ' 1is irreducible over the real number field, but reducible. ( x i)( x - i ) ,over the complex number field.

U S A MATHEMATICAL OLYMPIADS116Isoperimetric theorem for polygons.Among all n-gons with given area, the regular n-gon has the smallestperimeter. Dually, among all n-gons with given perimeter, the regularn-gon has the largest area.Jensen's inequality.If f ( x ) is convex in an interval I and w l , wz, ., w,, are arbitrarynon-negative weights whose sum is 1. thenw,f(x,) 2 f ( 2 )a2 f( W l X 1** Wnf(Xn) W2X2 . W,X,)* *for all x , in I.Matrix.A rectangular array of number ( a , , )Mean of n numbers.Arithmetic mean (aoerage) A . M . Geometric mean G .M . Harmonic mean H.M. ym1 "na,1-1, a, 2 0,a, oA . M . - G . M . - H . M . inequalitiesA . M . 2 G . M . 2 H . M . with equality if and only if all n numbersare equal.1 n*/rPower mean P ( r ) a : ] , a , 0, r # 0, Irl 00n 1-1 [ n a , ] " " if r o min(a,)if r -do max(a,)if r 00Special cases: P ( 0 ) G.M., P ( - 1) H . M., P ( 1 ) A . M .I t can be shown that P ( r ) is continuous on - 00 5 r I do, that is[lim P ( r ) r-0c[lim P ( r ) min(a,),r--mIim P( r ) max( a , ) .r-m- inequality.P ( r ) I P ( s ) for - do s r s s do, with equality if and only if allthe a , are equal. For a proof, see [120, pp. 76-77.]Menelaus ' theorem.If D , E , F, respectively, are three collinear points on the sidesB C , CA, A B of a triangle A B C , then(i)B D * C E . A F - D C * E A . FB.

117GLOSSARYConversely, if D , E, F , respectively are three points on the sidesBC, CA, A B o f a triangle ABC suitably extended, such that (i) holds,then D,E . F are collinear.Orthocenter of A A BC.Point of intersection of altitudes of AABCPeriodic function.f ( x ) is periodic with period a if f ( x a ) f ( x ) for all x.Pigeonhole principle ( Dirichlet 's box principle).If n objects are distributed among k n boxes, some box containsat least two objects.Polynomial in x of degree n.nFunction of the form P ( x ) c,x', cn # 0.1-0Irreducible-see IrreducibleRadical axis of two non-concentric circles.L

An Introduction to Inequalities by E. E Beckenbach and R. Bellman Geometric Inequalities by N. D. Kazarinoff . The Olympiad itself was to consist of five essay-type problems requiring mathematical power of the contestants and to be done in 3 hours (later changed to 3: hours). The purpose of the Olympiad was to discover and