Transcription
' rTHE USSROLYMPIADPROBLEMBOOI(rI,4SelecteclProblemsancl Theoremsof tzov,and l.M.YaglomThis book contains 320 unconventionalnumbertheoryand trigonometry.()-t,problenrsin algebra, arithrnctic, clcrntntaryof tht' problt'rrrs first appe:rrecl incompetitiveexaminations sponsorerd by thc School Matht'rrratit':rl Sot'it'ty of thcMoscow State University and in the Matlrcnratical ()lyrnpilrlshckl in Most.orv.Although most of the problems presupp()s('orrly lriglr st lrool rnlrllrt'rrrrtit's, tlrt'y rrrt'not easy; some are of uncommon difficrrlty :rrrrl will clrrlL'rrgc tlrc irrgt'nrrity ol rvr'llrvillrirrllrrr';rtlrolrrroIir':rlctlhigh school students and even advanct:rl scvcrrth :rrrtl t.iglrtlr {r:r,k'rs.l,Mostscr'li.rrs Arr,rrr11 llrtsr';rrr': llrtThe problems are grouped into twclvt's('l):lr:llldivisibilityof integers, equati lns lutvirtg irtlt'gcr solrrliorrs. r'rrrlrr:rlirrrl.rrrrrs:nrrlproducts, miscellaneous algebrait'prolrlt'ttts,lltr':rlg, lrr:r,,1 pr,l1 rr,,rrri:rls ,,,,rr1rl, rnumbers,problemsofntrmbt'rthtrrrlrlillcr, rrlr'\r'rlu{ nr'{ \,tlistirrr'livlirrcrlrrrlili.rand sums, and led from different llrlitrts ol r icu Solrrliorts lr) nr(,r( :r,lr.rrr, , ,1 ;rr,,lrllrrrs :t,lurtt,,,lr,trrr'pl,:rr,,trt;r1,,1,r1,I liirrr,\rrlrrr,interest to teachers clclrlirrg 'itlr r,,illcrl ;rrrrl r(l\:ilrr'r'(l I rr\\r'\rrrll1,,,,1 FIr-vT/ D ()(f,]IDlnllr, ,,1'1r,,rr,,,,,,,,',.,llr 1"rl'lislr,rlUnabridgedD o v c r ( 1 1 ) 1 ) : )t r ' l , t r l , l t , ; r l r , , r r , , i.l l,'r,rr,'rrllr'llr'llrrl(llrrssi:rrr)(llrrrrr.rrr) r'rlrtr,,rr l'.rlrt,'r ,, l,,r, rr,,rrl rations. xvi .lir2trp i,1,, li', l'.rl.r l,,,rrrrrlm(n,plr117wr-r'1: rpTHEUSSROLYMPIADPROBLEMBOOI(SelectedProblemsand r',1 ) , , r , r ( , , r r r 1 ' 1 ,l , \ l , l l ! ,,,,,l',,",1',,', 'r,,( .rl.rlor',,rr:rillrlrlt'rrltott rtrluest.r \8N 0-qBtr-?1 01-7aoaD.O.Shklarsl y,N.N.Chentzovand l.M.Yaglom5@?NililffiffI ililililill iltilililfitlo\o\'il,l,-'l',lNll\Ar:d"
DOVER BOOKS ONMATHEMATICSA Corcrsp HrsroRyoFMArrlEnaeucs,Dirk J. Struik. (6025b-g) Z.gISr.lrrsrrcer-Mprnoo rnou rrrn Vmweonrr or Quer,rrvCovrnol, Wtli.r,r A.Shewhart. (65232-7) 7 .95Vrcrnns, Tbtsons,u.u nu B.lsrc EqumoNs oF FLUrDMEcrrANrcs.Rutherford Aris. (661 10-5)98.95Tlrr TlunmrN Booxs otEucuo's Er,rrl,tnvrs,translated with anintroduction and commentary by Sir Thomas L. Heath.(60088-2, 60089-0, 60090-4) 29.85IvtnoougrroN ro P.IRTIALDF FERErtrur.Equlrroxs wrru Aler,rcertoNs;E.C. Zachmanoglouand DaIe W. Thoe. (652b1-B) 10.9bNul,mnrcer,Mrrrroos r.on Scmltrlsrs .cNDENcNEens, Richard Hamming.(65241-6) 15.95Onou.renyDrrrennNrrer, Equ.lrtors, Monris Tenenbaum and HarrvPollard. (64940-7) 18.95Tbowrc.lr, CercuLUSwm{ ANALyrrc GEoNc-rBy,Judith L. Gersting.(67343-X) 13.95Oscrr,r,lrroxsrNNorr,welln SyslEMs,Jack K. Hale. (62362-6) g?.gbGpepx M.l,rrrrlarrc.c,I, Tkoucrrr ervouc OnrcrNor ArcsgRA. Jacob Kle in .(27289-3) 9.95Fntrro DnrsRENcr EquerroNs,H. I-r.y & F. hssman. (67260-g) ?.gbAppuclnoNs or Fnvnr Gnor-rps,J. S. Lomont. (6Z8Z6-6)gg.gsArpr,rco hoeABrr-rry Moorrs wrnr Osrur.rzltrolr Appr,rc.lrroNs.SheldonM. Ross. (67314-6) 6.95l.rlnoouctroN lr rnr Cerrulus or Vmurrons, Hans Sagan.(67366-9) 12.95IvrnoousrroN ro PenrrAr,DnrnnsNTrAL EeuATroNs,Arne Broman.(66158-X) 6.95AN IrrnoousrroN tr ORDTNARyDu.r.ansNTrALEeuATloNS,Earl A.Coddinston. (65942-9) 8.95M.q,TRrcesANDLween ThetsroRMATroNS,Charles G. Cullen.(66328-0) 8.95DrrrBnpwrnr, Fonnrswtrn Appt tcATIoNSTo rlrE pxystcer. ScreNcEs.HarlevFlanders. (66169-5) 7.95Thnony exo Appr,rcATroNoF INFrrvnpSpnres, Konrad Knopp.(66165-2) 13.95AN I*rnopuctroN nr ArcnsRArc SrRUcruREs,Joseph Landin.(65940-2) ?.e5Getvms,rNoDecrsrous: IrrnooucuoN ANDCRrrrcALSr-nvpy, R. DuncanLuce and Howard Raiffa. (65943-?) 12.95Frnsr Oporn M.lrrculrrcel Locrc, Angelo Margaris. (66269-1) ?.95Ixrr.ooucrror,r ro Toeorocv, Bert Mendelson. (663b2-B) 96.9bGporvrsrRy:A ColrpnprnusrveCounsn,Dan pedoe. (6b812-0) g12.gsFuNcrrowar,Ar.rlr,ysrs,Frigyes Riesz and B6la Sz.-Nagy.(66289-6) 12.95(antinu.edon fuck flnp)
TI{E USSROLYMPIADPROBLEMBOOKProblcmsard TlrcoremsSelectedsof ElcmentaryMatlrcmaticD. O. SIKLARSKYN. N. CHENTZOVI. M. YAGI.,OMREVISEDAND EDITED BYInvnc SussMlN,Univcrsity S futrto ClaraTRANSTATEDBYJoHxMeYrovIcH,Univcrsityof funnClamiL., 'J-\ 5 fl,o".,0DOVERPUBLICATIONS,INC.NewYomv-L! "/ oo
FOREWORDTO THEPublished in Canada by General hrblishing Company, Ltd., 30 Lesmill Road,Don Mills, Toronto, Ontario.hrblished in the United Kingdom by Constable and Company, Ltd., 3 TheLanchesters,162-l& ftrlham FalaceRoad, London W6 9ER.THIRD (Russian)EDITIONBibliographical NoteThis Dover edition, first published in 1993, is an unabridged and unalteredrepublication of the work finst publish d by W.H. freeman and Company, Sanfrancisco, in1962.Library of CongressCataloging-in-PublicationDanShkliarskil, D. O. (David Oskarwich), lgt&-1942.fizbrannp zadrchi i tcoremy elementarnol matematiki, ch l. English]The USSR Olympiad problem book : selecrcd problems and-theorems ofelementary mathematics/ D.O. Shklarsky, N.N. Chentzor,,I.M. yaglom; translated by John Maykorrich.-3rd ed / rcv. and edited by Irving Sussman.p.cm.rsBN G48G27709-7l. Mathematics-hoblems, exercises,etc. I. Chentsov,N. N. (NikolalNikolaevich) tr. IAglom, I. M. (lsaak Moiseevich), l92l-.III. Sussman,Irving. IV. Trtle.QA43.S581319945lO'.7*dc20Manufactured in the United Statesof AmericaDover Publications,Inc., 3l East 2nd Street,Mineola N.y. ll50l93-11553CIPTnrs aoox coNrAINs320 unconventional problems in algebra, arithme'Most of thesetic, elementary number theory, and trigonometry.problems first appeared in competitive examinations sponsored by theSchool Mathematical Society of the Moscow State University and inthe Mathematical Olympiads held in Moscow. The book is designedfor students having a mathematical background at the high sghogllevel;r very many of the problems are within reach of seventh&6ndSolutions are giveneighth grhde students of outstanding ability.for all the problems. The solutions for the more difficult problemsare especially detailed.The third (Russian) edition differs from the second chiefly in theelimination of errors detected in the second edition. Therefore, thepreface to the second edition is retained.t The level of academic attainment referred to as "high school level" is theAmerican ninth to twelfth grades. The USSR equivalent is seventh to tenthgrades. This means that this material is introduced about two years earlierin the Russian schools. Since Russian children begin their first grade studiesabout a year later than do American children, the actual age disparity is notas much as two years l0ditorl.vil
PREFACETO THESECOND(Russian)EDITIONTHp rnBssNTvoLuuE,which constitutesthe first part of a collection,contains 320 problems involving principally algebra and arithmetic,although severalof the problemsare of a type meant only to encouragethe developmentof logical thought (see, for example, problems1-8).The problems are grouped into twelve separatesections. The lastfour sections(ComplexNumbers,SomeProblemsfrom Number Theory,and Series)contain important theoInequalities, Numerical Sequencesretical material, and they may well serve as study topics for schoolmathematical societiesor for the Societyon ElementaryMathematicsat the pedagogicalinstitutes. In this respectthe supplementaryrefer.encesgiven in various sectionswill also prove useful. All the othersections [especially Alterations of Digits in Integers and Solutionsof Equationsin Integers (Diophantineequations)lshouldyield materialprofitable for use in mathematicsclubs and societies.Of the twelve sections,only four (MiscellaneousProblemsin Algebra,Polynomial Algebra, ComplexNumbers, Inequalities)concernalgebra;the remaining sectionsdeal with arithmetic and number theory. Aspecial effort has beenmadeto play down problems(particularly thoseih algebra) inriolving detailid nianip-uldtivematter. This was doneto avoid dupliciting materiai in the eiCbllent ProblemBoohin Algebra.,.
vuiOlymbiad Problemsby V. A. Kretchmar (Government Technical Publishing House, Moscow1950). On the other hand, an effort has been made to render muchof the book attainable to eighth grade, and even seventh grade,students.More than three years have passed since the appearance of the firstedition of this book. During this period the original authors receiveda great many written and oral communications with respect to it,and these have been seriously considered in the reworking of thematerial and in deciding which features were worth retaining andemphasizing and which aspects were weak. As a result, the bookhas undergone considerable revision. About sixty problems that werein the first edition have been omitted-some appeared to be too difficult, or were insufficiently interesting, and others did not fit intothe new structure of the book. Approximately I20 new problems havebeen added. The placing of each problem into a suitable sectionhas been restudied; the sections have been repositioned; all the solutions have been reworked (several were replaced by simplified orbetter solutions); and alternative solutions have been provided forsome of the problems. Hints have been given for every problem,and those problems which to the authors appear of greater difficultyhave.been starred(*). Sections 3,5,6,9, and 10 have undergone suchsignificant changes that they may be considered as having been completely rewritten. Sections I,2, 4,7, and, 11 have been revised radically, and only Sections 8 and 12 have had relatively minor alterations.The first edition of the book was prepared by I. M. Yaglom incollaboration with G. M. Adelson-Vel'sky (who contributed the sectionon alteration of digits in integers and also a number of problems toother sections, particularly to the section on Diophantine equations).An important contribution was made to the first edition by E. E.Balash (who contributed the section on numerical sequencesand series)and Y. I. Khorgin (who made the principal contribution to the sectionon inequalities). Solutions for other problems were written by variousdirectors of the School Mathematical Society of the Moscow StateUniversity.About 20 problems were taken from manuscripts of thelate D. O. Shklarsky.The rewriting of the book for the second edition was done by I.M. Yaglom, who made extensive use of the material of the firstIn conclusion, the author wishes to thank A. M. Yaglom, whoseadvice was of invaluable assistance while the book was being writtenand who initiated the rewriting of the section on complex numbers.Preface to the Second EditionixThe author is also indebted to the editor, A. Z. Rivkin, whose indefatigable labors on the first and second editions made possible manyimprovements, and to all the readers who made valuable suggestions,especially I. V. Volkova, L. I. Golovina, R. S. Guter, G. Lozanovsky,I. A. Laurya, Y. B. Rutitsky, A. S. Sokolin, and I. Y. Tanatar.I. M. Yaglom
EDITOR'SFOREWORDTO THEENGLISHEDITIONOne of the important facets of scienceeducation in the USSR hasbeentheir series of mathematical competitive examinations held forstudents of high ability in the secondary schools. Those contests,which are being emulatedincreasingly in our own educationalsystem,culminate eagh year in the Soviet Union in their MathematicalOlympiads held at Moscow University, preliminary qualifying andelimination examinations having beenheld nationwide throughout theacademicyear.This book, compiled over a twenty-year period, is a collection ofthe most interesting and instructive problemsposedat these competitions and in other examinationcentersof the USSR,plus additionalproblemsand material developedfor use by the fthool MathematicsStudy Societies. Perhaps the greatestcompliment which can be paidto the problems createdfor this purposeby leading Soviet mathema'ticians (or tikeii ahd adaptedfrom the literature) has been the extentto which the problems have been used in our own contests and ex'aminations.Soviet students and teachers have had available in published formthe problems, and their solutions, given in such examinations, butthis material has not generally been available in the United States.
xrrOfumpiad problemA few of these problems have been translated and published in suchAmerican journals as The American Mathematicat Monthly of rheMathematical Association of America, and problems of similar scopeappear as regular features of Several American journals. Except forsome compilations from these sources, little exists by way of problemswhich deal with real and active mathematics instead of the fringeand recreational aspects of the scienceor with conventional textbookexercises.This translation and revision of the Third Revised and AugmentedEdition of the olympiad Problem Book should therefore fill a verydefinite need in American schools and colleges. It contains 320problems-a few of them merely recreational and thought-provoking,but most of them seriously engaged with solid and importantmathematical theory, albeit the preparational background is assumedto be elementary. The problems are from algebra, arithmetic,trigonometry, and number theory, and all of them emphasize thecreative aspects of these subjects. The material coordinates beautifully with the new concepts which are being emphasizedin Americanschools, since the "unconventional" designation attributed to theproblems by the original authors means that they stress originalityof thought rather than mere manipulative ability and introduce thenecessity for finding new methods of attack.In this respect I am reminded of the observation made by someforgotten character in some forgotten novel who opined that theultimate test of an educative effort lay not nearly so much in whatsort of questions the students could finally answer as in what sortof questions they could finally be asked!Complete solutions to all problems are given; in many cases,alternate solutions are detailed from different points of view.Although most of the problems presuppose only high school mathematics, they are not in any sense easy: some are of uncommondifficulty and will challenge the ingenuity of any research mathematician. on the other hand, many of the problems will yield readilyto a normally bright high school student willing to use his head.Where more advanced concepts are employed, the concepts are discussed in the section preceding the problems, which gives the volumethe aspect of a textbook as well as a problem book. The solutionsto more advanced problems are given in considerable detail.Hence this book can be put to use in a variety of ways for studentsof ability in high schools and colleges. In particular, it lends itselfexceptionally well to use in the various Institutes for high schoolEditor's Foreword to the English Editionxiiimathematics teachers. It is certainly required reading for teachersdealing with the gifted student and advanced placement classes. Itwill furnish them with an invaluable fund for supplementary teachingmaterial, for self-study, and for acquiring depth in elementarymathematics.Except for the elimination of the few misprints and errors foundin the original, and some recasting of a few proofs which did notappear to jell when translated literally, the translation is a faithfulone: it was felt that the volume would lose something by too muchtampering. (For this reason the original foreword and preface havealso been retained). Thus the temptation to radically alter or simplifyany understandable solution was resisted (as, for example, in thesections on number theory and inequalities, where congruencearithmetic would certainly have supplied some neater and more directproofs). Some notations which differ in minor respects from thestandard American notations have been retained (as, for example,C* instead of Cl). These will cause no difficulty.All references made in the text to books not available in Englishtranslation have been retained; no one can know when translationsof some of those volumes will appear. Whenever an English trans'lation was known to exist, the translated edition is referred to.The translation was made from the Third (Russian) Edition ofSelected Problems and Theorems of Elernentary Mathernatics, whichis the title under which the original volume appeared in the SovietUnion. Mr. John Maykovich, instructor at the University of SantaClara, was the translator, and he was assisted by Mrs. Alvin (Myra)White, who translated fifty pages. The writing out, revising, editing,annotating, and checking against the original Russian were by myown hand.Thanks are due the following persons for their assistancein readingportions of the translation, pointing out errors, and making valuablesuggestions: Professor George Polya of Stanford University,r ProfessorAbraham Hillman of the University of Santa Clara, and ProfessorRobert Rosenbaum of Wesleyan University.I shall be very grateful to readers who are kind enough to pointout errors, misprints, misleading statements of problems, and incorrect or obscure proofs found in this edition.January 1962Irving Sussmant I would also like to call attention to Professor Polya's new book Mathtmotinal Di,saaerg (Wiley) which contains elementary problems and valuabletextual discussion of approaches to, and techniques of, problem solving'
&CONTENTSForeword to the Third (Russian)EditionPreface to the Second (Russian) EditionEditor's Foreword to the English EtlitionFrom the AuthorsSuggestionsfor Using this BookNumerical Referenceto the Problems Given in the MoscowMathematical Olympiads1. Introductory Problems (1-14)2. Alterations of Digits in Integers (15-26)3. The Divisibility of Integers (27-7I)4. Some Problems from Arithmetic (72-109)5. Equations Having Integer Solutions (110-130)6. Evaluating Sums and Products (131-159)7. MiscellaneousProblems from Algebra (1@-195)8. The Algebra of Polynomials (19G22f)9. Complex Numbers (Zn-29)vviixiI3c6111320273038,t550xv
xvi10. Some Problems of Number Theory en-ZS4)1 1 . Some Distinctive Inequalities (2S -30g)t2. Difference Sequencesand Sums (309-320)SolutionsAnswers and HintsOllttnfiad Problems56617480423FROM THE onofproblemsare the commencementof a series of books based on materialg"trr"i"a by the school Mathematics society of.the Moscow stsofproblemsmeetingsand theorems, most of which have been presentgdduringof theSocietyMathematicalof the various sections of the SchoolMoscow'inheldOlympiadsIA.S.U. as well as in the Mathematical(The numbersof the problems given in the Olympiads are listed onp. 5).ofThese volumes are directed to students, teachers, and directorsschoolmathematicalsocietiesand societieson elementarymathematics(Part I) containsoi tf," pedagogical institutes. The first volumeThe secondtheory'problems in arittrmetic, algebra, and numberthird tothegeometry,andplanevolume is devoted to problems inproblems in solid ndedforhightheschool students, these books are designednot only to reinforcemethodswithhimacquainttoalsobutstudent's formal knowledge,and ideasnew to him and to develop his predilection for, and abilityin, original thinking. Here, there are few problemswhosesolutionsI
TI{E USSR OLYMPIAD PROBLEM BOOK Selected Problcms ard Tlrcorems of Elcmentary Matlrcmatic s D. O. SIKLARSKY N. N. CHENTZOV I. M. YAGI.,OM REVISED AND EDITED BY Invnc SussMlN, Univcrsity S futrto Clara TRANSTATED BY JoHx MeYrovIcH, Univcrsity of funnClam J-\ 5 fl, o".,0 iL. , ' DOVER PUBLICATIONS, INC. New Yom v-L ! "/ oo
