Transcription

101 PROBLEMS IN ALGEBRAFROM THE TRAINING OF THE USA IMO TEAMT ANDREESCU t Z FENDAMT PUBLISHING

101 PROBLEMS IN ALGEBRAFROM THE TRAINING OF THE USA 1MO TEAMT ANDRUSCU Ft Z FFNG

Published byAMT PUBLISHINGAustralian Mathematics TrustUniversity of Canberra ACT 2601AUSTRALIACopyright 2001 AMT PublishingTelephone: 61 2 6201 5137AMTT Limited ACN 083 950 341National Library of Australia Card Number and ISSNAustralian Mathematics Trust Enrichment Series ISSN 1326-0170101 Problems in Algebra ISBN 1 876420 12 X

THE AUSTRALIAN MATHEMATICS TRUSTENRICHMENT S E R I E SEDITORIAL COMMITTEEChairmanEditorGRAHAM H POLLARD, Canberra AUSTRALIAPETER J TAYLOR, Canberra AUSTRALIAWARREN J ATKINS, Canberra AUSTRALIAED J BARBEAU, Toronto CANADAGEORGE BERZSENYI, Terra Haute USARON DUNKLEY, Waterloo CANADAWALTER E MIENTKA, Lincoln USANIKOLAY KONSTANT1NOV, Moscow RUSSIAANDY Liu, Edmonton CANADAJORDAN B TABOV, Sofia BULGARIAJOHN WEBB, Cape Town SOUTH AFRICAThe books in this series are selected for their motivating, interestingand stimulating sets of quality problems, with a lucid expository stylein their solutions. Typically, the problems have occurred in eithernational or international contests at the secondary school level.They are intended to be sufficiently detailed at an elementary levelfor the mathematically inclined or interested to understand but, atthe same time, be interesting and sometimes challenging to theundergraduate and the more advanced mathematician. It is believedthat these mathematics competition problems are a positiveinfluence on the learning and enrichment of mathematics.

THE AUSTRALIAN MATHEMATICS TRUSTENRICHMENTSERIESBooKs IN THE SERIES1AUSTRALIAN MATHEMATICS COMPETITION BOOK 1 1978-1984JD Edwards, DJ King Et PJ O'Halloran2MATHEMATICAL TOOLCHESTAW Plank Et NH Williams3TOURNAMENT OF TOWNS QUESTIONS AND SOLUTIONS 1984-1989PJ Taylor4AUSTRALIAN MATHEMATICS COMPETITION BOOK 2 1985-1991PJ O'Halloran, G Pollard Et PJ Taylor5PROBLEM SOLVING VIA THE AMCW Atkins6TOURNAMENT OF TOWNS QUESTIONS AND SOLUTIONS 1980-1984PJ Taylor7TOURNAMENT OF TOWNS QUESTIONS AND SOLUTIONS 1989-1993PJ Taylor18ASIAN PACIFIC MATHEMATICS OLYMPIADS 1989-2000H Lausch Et C Bosch Giral9METHODS OF PROBLEM SOLVING BOOK 1JB Tabov Ft PJ Taylor10 CHALLENGE! 1991-1995JB Henry, J Dowsey, AR Edwards, U Mottershead,A Nakos Et G Vardaroii1 12USSR MATHEMATICAL OLYMPIADS 1989-1992AM SlinkoAUSTRALIAN MATHEMATICAL OLYMPIADS 1979-1995H Lausch Et PJ Taylor13CHINESE MATHEMATICS COMPETITIONS AND OLYMPIADS 1981-1993A Liu

114 POLISH Et AUSTRIAN MATHEMATICAL OLYMPIADS 1981- 1995ME Kuczma Et E Windischbacher115TOURNAMENT OF TOWNS QUES11ONS AND SOLUTIONS 1993-1997PJ Taylor Et AM Storozhev116AUSTRALIAN MATHEMATICS COMPETITION BOOK 3 1992-1998WJ Atkins, JE Munro Et PJ Taylor17SEEKING SOLUTIONSJC Burns18101 PROBLEMS IN ALGEBRAT Andreescu Et Z Feng

PREFACEThis book contains one hundred highly rated problems used in the training and testing of the USA International Mathematical Olympiad (IMO)team. It is not a collection of one hundred very difficult, impenetrablequestions. Instead, the book gradually builds students' algebraic skillsand techniques. This work aims to broaden students' view of mathematics and better prepare them for possible participation in various mathematical competitions. It provides in-depth enrichment in important areasof algebra by reorganizing and enhancing students' problem-solving tac-tics and strategies. The book further stimulates students' interest forfuture study of mathematics.

INTRODUCTIONIn the United States of America, the selection process leading to participation in the International Mathematical Olympiad (IMO) consistsof a series of national contests called the American Mathematics Contest 10 (AMC 10), the American Mathematics Contest 12 (AMC 12),the American Invitational Mathematics Examination(AIME), and theUnited States of America Mathematical Olympiad (USAMO). Participation in the AIME and the USAMO is by invitation only, based onperformance in the preceding exams of the sequence. The Mathematical Olympiad Summer Program (MOSP) is a four-week, intense training of 24-30 very promising students who have risen to the top of theAmerican Mathematics Competitions. The six students representing theUnited States of America in the IMO are selected on the basis of theirUSAMO scores and further IMO-type testing that takes place duringMOSP. Throughout MOSP, full days of classes and extensive problemsets give students thorough preparation in several important areas ofmathematics. These topics include combinatorial arguments and identities, generating functions, graph theory, recursive relations, telescopingsums and products, probability, number theory, polynomials, theory ofequations, complex numbers in geometry, algorithmic proofs, combinatorial and advanced geometry, functional equations and classical inequalities.Olympiad-style exams consist of several challenging essay problems. Cor-rect solutions often require deep analysis and careful argument. Olympiad questions can seem impenetrable to the novice, yet most can besolved with elementary high school mathematics techniques, cleverly applied.Here is some advice for students who attempt the problems that follow.Take your time! Very few contestants can solve all the given problems.Try to make connections between problems. A very importanttheme of this work is: all important techniques and ideas featuredin the book appear more than once!Olympiad problems don't "crack" immediately. Be patient. Trydifferent approaches. Experiment with simple cases. In some cases,working backward from the desired result is helpful.Even if you can solve a problem, do read the solutions. They maycontain some ideas that did not occur in your solutions, and they

viiiIntroductionmay discuss strategic and tactical approaches that can be used elsewhere. The formal solutions are also models of elegant presentation that you should emulate, but they often obscure the torturousprocess of investigation, false starts, inspiration and attention todetail that led to them. When you read the solutions, try to reconstruct the thinking that went into them. Ask yourself, "Whatwere the key ideas?" "How can I apply these ideas further?"Go back to the original problem later, and see if you can solve itin a different way. Many of the problems have multiple solutions,but not all are outlined here.All terms in boldface are defined in the Glossary. Use the glossaryand the reading list to further your mathematical education.Meaningful problem solving takes practice. Don't get discouragedif you have trouble at first. For additional practice, use the bookson the reading list.

ACKNOWLEDGEMENTSThanks to Tiankai Liu who helped in proof reading and preparing solutions.Many problems are either inspired by or fixed from mathematical contestsin different countries and from the following journals:High-School Mathematics, ChinaRevista Matematica TimiĀ§oara, RomaniaKvant, RussiaWe did our best to cite all the original sources of the problems in the solution part. We express our deepest appreciation to the original proposersof the problems.

ABBREVIATIONS AND AMOMOSPPutnamSt. PetersburgAmerican High School MathematicsExaminationAmerican Invitational MathematicsExaminationAmerican Mathematics Contest 10American Mathematics Contest 12,which replaces AHSMEAmerican Regional Mathematics LeagueInternational Mathematical OlympiadUnited States of America Mathematical OlympiadMathematical Olympiad Summer ProgramThe William Lowell Putnam MathematicalCompetitionSt. Petersburg (Leningrad) MathematicalOlympiadNotations for Numerical Sets and FieldsZthe set of integersthe set of integers modulo nthe set of positive integersthe set of nonnegative integersthe set of rational numbersthe set of positive rational numbersthe set of nonnegative rational numbersthe set of n-tuples of rational numbersthe set of real numbersthe set of positive real numbersthe set of nonnegative real numbersthe set of n-tuples of real numbersthe set of complex numbers

ABBREVIATIONS AND NOTATIONS1. INTRODUCTORY PROBLEMS2. ADVANCED PROBLEMSxiii1133. SOLUTIONS TO INTRODUCTORY PROBLEMS 274. SOLUTIONS TO ADVANCED PROBLEMS65GLOSSARY131FURTHER READING137

INTRODUCTORY PROBLEMS

1. INTRODUCTORY PROBLEMSProblem 1Let a, b, and c be real and positive parameters. Solve the equationa bx b cx c ax b -ax c-bx a-cx.Problem 2Find the general term of the sequence defined by x0 3, x1 4 andaxn 1 xn 1 - nxnfor all' n E N.Problem 3Let x1, x2i . , X. be a sequence of integers such that(i) -1 x, 2, for z 1, 2. , n;(ii) x1 x2 xn19;(iii)Determine the minimum and maximum possible values ofxi x2 xn.Problem 4The function f, defined byf(x) ax bcx d'where a, b, c, and d are nonzero real numbers, has the propertiesf (19) 19,f (97) 97,for all values of x, except -Find the range of f.dcandf (f (x)) x,

1. Introductory Problems2Problem 5Prove that\ a (a-b)2(a-b)2 a b-8a8b2for all a b 0.Problem 6Several (at least two) nonzero numbers are written on a board. One mayerase any two numbers, say a and b, and then write the numbers a 2and b - a instead.2Prove that the set of numbers on the board, after any number of thepreceding operations, cannot coincide with the initial set.Problem 7The polynomial1-x x2-x3 . x16 x17may be written in the formao a1y a2y2 . a16y16 a17y17,where y x 1 and as are constants.Find a2.Problem 8Let a, b, and c be distinct nonzero real numbers such thata b b -c c -.111Prove that Iabcl 1.Problem 9Find polynomials f (x), g(x), and h(x), if they exist, such that for all x,1 -1If (x) I - I g(x) I h(x) 3x 2ifx -1if -1 x 0-2x 2 ifx 0.

1. Introductory Problems3Problem 10Find all real numbers x for which8x 27"12x 18x76Problem 11Find the least positive integer m such thatfor all positive integers n.Problem 12Let a, b, c, d, and e be positive integers such thatabcde a b c d e.Find the maximum possible value of max{a, b, c, d, e}.Problem 13Evaluate3200141! 2! 3! 2! 3! 4!1999! 2000! 2001!Problem 14Let x vfa2 a 1-'1a2 --a 1, a ER.Find all possible values of x.Problem 15Find all real numbers x for which10x 1lx 12x 13x 14x.

1. Introductory Problems4Problem 16Let f : N x N - N be a function such that f (1, 1) 2,f(m 1,n) f(m,n) m and f(m,n 1) f(m,n)-nfor all m,nEN.Find all pairs (p, q) such that f (p, q) 2001.Problem 17Let f be a function defined on [0, 1] such thatf (O) f(l) 1 and I f (a) - f (b)I I a - bI,for all ab in the interval [0, 1].Prove thatIf(a)-f(b)I 2Problem 18Find all pairs of integers (x, y) such thatx3 y3 (x y)2.Problem 19Let f (x) 24x2for real numbers x.Evaluatef(2001I) f(20012) f (20001)Problem 20Prove that for n 6 the equation1x1 1x22 . 1x2 1has integer solutions.Problem 21Find all pairs of integers (a, b) such that the polynomial ax17 bxls 1is divisible by x2 - x - 1.

1. Introductory Problems5Problem 22Given a positive integer n, let p(n) be the product of the non-zero digitsof n. (If n has only one digit, then p(n) is equal to that digit.) LetS p(1) p(2) p(999).What is the largest prime factor of S?Problem 23Let xn be a sequence of nonzero real numbers such thatxi 2xn 1xn2xn 2 - xn 1for n 3, 4, .Establish necessary and sufficient conditions on x1 and x2 for x., to bean integer for infinitely many values of n.Problem 24Solve the equationx3-3x x 2.Problem 25For any sequence of real numbers A {a1, a2, a3, }, define DA to bethe sequence {a2 - a1, a3 - a2, a4 - a3, .}. Suppose that all of the termsof the sequence A(AA) are 1, and that a19 a92 0.Find a1.Problem 26Find all real numbers x satisfying the equation2x 3x-4x 6x-9x 1.Problem 27Prove that8016 Ev1k 1 17.kProblem 28Determine the number of ordered pairs of integers (m, n) for which mn 0 andm3 n3 99mn 333.

1. Introductory Problems6Problem 29Let a, b, and c be positive real numbers such that a b c 4 andab bc ca 4.Prove that at least two of the inequalitiesla - bi 2,lb - cl 2,Ic - al 2are true.Problem 30Evaluaten1E (n - k)!(n k)!k OProblem 31Let 0 a 1. Solvefor positive numbers x.Problem 32What is the coefficient of x2 when(1 x)(1 2x)(1 4x).(1 2 nX)is expanded?Problem 33Let m and n be distinct positive integers.Find the maximum value of Ix' - xnl where x is a real number in theinterval (0, 1).Problem 34Prove that the polynomial(x - al)(x - a2).(x - an) - 1,where al, a2,, an are distinct integers, cannot be written as the product of two non-constant polynomials with integer coefficients, i.e., it isirreducible.

1. Introductory Problems7Problem 35Find all ordered pairs of real numbers (x, y) for which:(1 x)(1 x2)(1 x4) l y7and(1 y)(1 y2)(1 y4) 1 x7.Problem 36Solve the equation2(2x - 1)x2 (2x-2 - 2)x 2x 1 - 2for real numbers x.Problem 37Let a be an irrational number and let n be an integer greater than 1.Prove that(a a2-1) (a - a2-1)is an irrational number.Problem 38Solve the system of equations(x1 - x2 x3)2 x2(x4 x5 - x2)(x2 - x3 x4)2 x3(x5 x1 - x3)(x3 - x4 x5)2 x4(x1 x2 - x4)(x4 - x5 x1)2 x5(x2 x3 - x5)(x5 - x1 x2)2 xl(x3 x4 - xl)for real numbers x1, x2, x3, x4, x5.Problem 39Let x, y, and z be complex numbers such thatx y z 2,x2 y2 z2 3andxyz 4.Evaluate111xy z-l yz x-l zx y-1

1. Introductory Problems8Problem 40Mr. Fat is going to pick three non-zero real numbers and Mr. Taf is goingto arrange the three numbers as the coefficients of a quadratic equationx2 x 0.Mr. Fat wins the game if and only if the resulting equation has twodistinct rational solutions.Who has a winning strategy?Problem 41Given that the real numbers a, b, c, d, and e satisfy simultaneously therelationsa b c d e 8 and a2 b2 c2 d2 e2 16,determine the maximum and the minimum value of a.Problem 42Find the re