Scribd
Upload
366 views343 pages

Problem Solving Through Problems - Larson PDF

Uploaded by

jun
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
366 views343 pages

Problem Solving Through Problems - Larson PDF

Uploaded by

jun
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
Problem Books in Mathematics Series Editor: P.R. Halmos Unsolved Problems in Intuitive Mathematies, Volume I: Unsolved Problems in Number Theory by Richard K. Guy 1981. xviii, 161 pages. 17 illus. ‘Theorems and Problems in Functional Analysis by A.A. Kirillov and A.D. Gvishiani (trans. Harold H. MeFaden) 1982. ix, 347 pages. 6 illus. Problems in Analysis by Bernard Gelbaum 1982. vii, 228 pages. 9 illus. A Problem Seminar by Donald J. Newman 1982. viii, 13 pages. Problem-Solving Through Problems by Loren C. Larson 1983. xi, 344 pages. 104 illus. Loren C. Larson Problem-Solving Through Problems With 104 Iustrations Springer-Verlag S$ New York Berlin Heidelberg Tokyo Loren C, Larson Department of Mathematics St. Olaf College ‘Northfield, MN 55057 USA. Editor Paul R. Halmos Department of Mathematics Indiana University Bloomington, IN 47405 USA. AMS Classification (1981): 00407 Library of Congress Cataloging in Publication Data Larson, Loren C,, 1937- Problem-solving through problems. (Problem books in mathematics) 1. Mathematies—Problems, exereses, etc. 1. Title, IL Series. QAGL37 1983 51082-19493 Problem solving. (© 1983 by Springer-Verlag New York Inc. All rights reserved. No part of this book may be translated or reproduced im any form without writen permission from Springer-Verlag, 175 Fifth Avenue, New York, New York 10010, USA. ‘Typeset by Computype, St. Paul, Minnesota Printed and bound by R. R. Donnelley & Sons, Harrisonburg, Virginia. Printed in the United States of America. 987654321 ISBN 0-387-90803.X Springer-Verlag New York Berlin Heidelberg Tokyo ISBN 3-540.90803-X Springer-Verlag Beclin Heidelberg New York Tokyo To Elizabeth Preface ‘The purpose of this book is to isolate and draw attention to the most important problem-solving techniques typically encountered in undergradu- ‘ate mathematics and to illustrate their use by interesting examples and problems not easily found in other sources. Each section features « single idea, the power and versatility of which is demonstrated in the examples and reinforced in the problems. The book serves as an introduction and snide to the problems literature (€.. as found in the problems sections of undergraduate mathematics journals) and as an easily accessed reference of, ‘essential knowledge for students and teachers of mathematics. “The book js both an anthology of problems and 2 manual of instruction, Ir contains over 700 problems, over one-third of which are worked in de Each problem is chosen for its natural appeal and beauty, but primasily for its unique challenge. Each is included to provide the context for illustrating 4 given problem-solving method. The sim throughout is to show how a basic set of simple techniques can be applied in diverse ways to solve an enormous variety of problems. Whenever possible, problems within sections are chosen to cit across expected course boundaries and to thereby strengthen the evidence that a single intuition is capable of broad applica tion, Each section concludes with “Additional Examples" that point to other contexts where the technique is appropriate. ‘The book is written at the upper undergraduate level. Tt assumes a rudimentary knowledge of combinatorics, number theory, algebra, analysis, ‘and geometry. Much of the content is accessible to students with only a year of calculus, and a sizable proportion does not even require this. However, most of the problems are at 2 level slightly beyond the usual contents of textbooks. Thus, the material is especially appropriate for students preparing for mathematical competitions. vm Preface ‘The methods and problems featured in this book are drawn from my ‘experience of solving problems at this level. Each new issue of The American Mathematical Monshly (and other undergraduate journals) con- tains material that would be just right for inclusion. Because these ideas ‘continue to find new expression, the reader should regard this collection as a starter set and should be encouraged to create @ personal file of problems and solutions to extend this beginning in both breadth and depth. Obvi- ‘ously, we can never hope to develop a “system” for problem-solving; however, the acquiring of ideas is a valuable experience at all stages of development Many of the problems in this book are old and proper referencing is very difficult. 1 have given sources for those problems that have appeared more recently in the literature, citing contests whenever possible, I would appreci- ate receiving exact references for those Ihave not mentioned. T wish to take this opportunity 10 express my thanks to colleagues and students who have shered many hours of enjoyment working on these problems. In this regard I am particularly grateful 10 O. E. Stenaitis, Professor Emeritus of St. Olaf College. Thanks to St. Olaf College and the Mellon Foundation for providing two summer grants to help support the ‘writing of this manuseript. Finally, thanks 0 all individuals who contcib- uted by posing problems and sharing solutions. Special acknowledgement goes to Murray $. Klamkin who for over a quarter of a century has stood 4s a giant in the area of problem-solving and from whose problems and solutions T have Jeamed a great deal. March 21, 1983 Lowes C. Larson Contents lagter 1. Howie th 13. 14. 1s. 16. 17. 18, 19. 110, LLL. Search for a Pattern Draw a Figure Formulate an Equivalent Problem Modify the Problem Choose Effective Notation Exploit Symmetry Divide into Cases Work Backward ‘Argue by Contradiction Pursue Parity Consider Exireme Cases 1.12. Generalize Copter 2. wo laportant Principles: Induction snd Pigsonhole Fry 23. 24. 25, 26. Induction: Build on P(A) Induction: Set Up P(E + 1) Strong Induction Induction and Generalization Recursion Pigconhole Principle Chapter 3. Arithmetic 3. 32. Greatest Common Divisor Modular Arithmetic PSSSSSSOR Gene 38 o 4 7” 84 a x Contents 3.3. Unique Factorization 100 3.4. Positional Notation 106 3.5. Arithmetic of Complex Numbers 14 120 I 42. Unique Factorization of Polynomials 125 43. ‘The Identity Theorem 132 44, Abstract Algebra 144 ‘Chaner 5. Sammaton of Series 154 Binominal Coefficients 154 52, Goomeure Sres 164 5.3. Telescoping Series 170 5A. Power Series 176 (Chapter 6. Intermediate Real Analysis 192 6.1. Continuous Funetions 192 62. The Intermediate-Value Theorem 198 63, The Derivative 203, 64. The Extreme-Value Theorem 206 6.5. Rolle’s Theorem 20 6.6. The Mean Value Theorem 216 67. L’H6pital’s Rule 25 68. The Integral 227 69, The Fundamental Theorem 234 ager. Nnaien m1 Basic Inequality Properties 241 72, Ashmetee Mean. Geomere-Mesn Inequality 248 73. Cauchy-Schwarz Inequality 254 7.4. Functional Considerations 259 73, Inequalities by Series 268, 76, ‘The Squeeze Principle mn ‘Chapter 8 Geometry 230 8.1. Classical Plane Geometry 280 82. Analytic Geometry 291 8.3. Vector Geometry 299 84, Complex Numbers in Geometry 312 ‘Conese xi Glossary of Symbols and Definitions 37 ‘Sources 319 Index 331 Chapter 1. Heuristics Strategy or tactics in problem-solving is called heuristics. In this chapter we will be concerned with the heuristies of solving mathematical problems. ‘Those who have thought about heuristics have described a number of basic ideas that are typically useful. Among these, we shall focus on the follow- ing: (0) Search for a pattern, (2) Draw a figure. 3) Formulate an equivalent problem. (4) Modify the problem, (5) Choose effective notation, (6) Exploit symmetry. (2) Divide into cases. (8) Work backward. (9) Argue by contradiction. (10) Pursue parity. (UD Consider exireme cases. (12) Generalize. ‘Our interest in this list of problem-solving ideas is not in their descrip- tion but in their implementation. By looking at examples of how others have used these simple but powerful ideas, we can expect to improve our problem-solving skills. Before beginning, a word of advice about the problems at the end of the sections: Do not be overly concemed about using the heuristic treated in that section. Although the problems are chosen to give practice in the use ‘of the heuristic, a narrow focus may be psychologically debilitating.“ A single problem usually admits several solutions, often employing quite 2 1. eoristies different heuristics. Therefore, itis best to approach each problem with an ‘open mind rather than with a preconceived notion about how a particul heuristic should be applied. In working on a problem, solving it is what ‘matters. It is the accumulated experience of all the ideas working together that will result in a heightened awareness of the possibilities in a problem. 1.1. Search for a Pattern Virtually all problem solvers begin their analysis by getting a feel for the problem, by convincing themselves of the plausibility of the result. This is best done by examining the most immediate special cases; when this exploration is undertaken in a systematic way, patterns may emerge that will suggest ideas for proceeding with the problem, AA. Prove that a set of m (different) elements has exactly 2" (different) subsets, ‘When the problem is set in this imperative form, a beginner may panic and not know how to proceed. Suppose, however, that the problem were cast as a query, such as (i) How many subsets can be formed from a set of n objects? Gi) Prove of disprove: A set with m elements has 2” subsets. In either of these forms there is already the implicit suggestion that one should begin by checking out a few special cases. This is how each problem should be approached: remain skeptical of the result until convinced. Solution 1, We begin by examining what happens when the set contains 0,1,2,3 elements; the results are shown in the following table: Elements Number of n of S Subsets of S subsets of S 0 none @ T Tox 2 (x1) 2 2 oxye {xi Ga} (te ¥a) 4 Boxpxpta (my) (rhs (utah 8 Aaah nas}, Cents) (ta) (Our purpose in constructing this table is not only to verify the result, but ‘also to Took for patterns that might suggest how to proceed in the general 1, Seareh fora Patera 3 case. Thus, we aim to be as systematic as possible. In this case, notice when = 3, we have listed first the subsets of (x,,x3} and then, in the second line, each of these subsets augmented by the element x,. This is the key idea that allows us to proceed to higher values of n. For example, when n= 4, the subsets of S = (xy, x3,%),%2} are the eight subsets of {x,%3,%3} ‘(shown in the table) together with the eight formed by adjoining x, to cach of these. These sixteen subsets constitute the entire collection of possibili- ties; thus, a set with 4 elements has 2* (= 16) subsets. ‘A proof based on this idea is an easy application of mathematical induction (see Section 2.1). Solution 2, Another way to present the idea of the last solution is to argue as follows. For each n, let 4, denote the number of (different) subsets of a set with 1 (different) elements. Let $ be a set with + elements, and designate one of its elements by x. There is a one-to-one correspondence between those subsets of $ which do not contain x and those subsets that do contain x (namely, a subset 7 of the former type corresponds to T U(x). The former types are all subsets of S— {x}, a set with elements, and therefore, it must be the case that Ayes = 2Ay. ‘This recurrence relation, true for =0,1,2.3,---, combined with the fact that 4j= 1, implies that A,— 2". (4, = 24,;= 24, pees = 2g =2) Solution 3. Another systematic enumeration of subsets can be cartied out by constructing a “tree”. For the case n = 3 and S= (a,b,c}, the tree is as shown below: Sate ¢ a3 2 can be written as a sum of two perfect squares (p= m? + n?, with m and integers) if and only if p is one more than a mulliple of 4. Make a conjecture concerning which primes p >2 can be written in each of the following forms, using (not necessarily positive) integers x and y: (a) x? + 16,2, (b) 4x? + 4xy + 572, (See 1.5.10.) LALIL. If (a,> is @ sequence such that form > 1, 2—a,)a,44= 1, what happens toa, as n tends toward infinity? (See 7.6.4.) ‘1.1.12, Let S be a set, and let * be a binary operation on § satisfying the laws yex xe(xey)=y — forallx, yin S, Gexexsy — forallx,yins. © eT PG Show that x¢y = ye.x forall x,y in S. nat 4) ye oral = sifpers sou 3 Most induction problems are based on the discovery of a pattern. Thus, the problems in Sections 2.1, 22, 23, 2.4 offer additional practice im this heuristic, Also see 1.7.2, 1.7.7, 1.78, 2.5.6, 3.11, 346, 43.1, 44.1, 443, 44.15, 44.16, 4.4.17. Additional Examples * 1.2. Draw a Figure 9 1.2. Draw a Figure ‘Whenever possible it is helpful to describe a problem pictorially, by means ‘of a figure, a diagram, or a graph. A diagrammatic representation usually makes it casier (0 assimilate the relevant data and to notice relationships and dependences. 1.21, A chord of constant Iength slides around in @ . The midpoint of the chord and the projections of its ends upon the base form the vertices of a triangle. Prove that the triangle is isosceles and never changes its shape. Solution, Let AB denote the base of the semicircle, et XY be the chord, M the midpoint of XY, C and D the projections of X and ¥ on AB (Figure 1.1), Let the projection of M onto AB be denoted by N. Then W is the midpoint of CD and it follows that A CMD is isosceles. To show that the shape of the triangle is independent of the position of the chord, it suffices to show that 2 MCD remains unchanged, or equiva- Jently, that 2 XCM is constant, for all positions of XY. To see that this is the case, extend XC to cut the completed circle at Z (Figure 1.2). Then CM is parallel to ZY (C and M are the midpoints of XZ and XY, respectively), x tee “x 10 1, Heoristies and consequently ZXCM = 2 XZY. But 2 XZY equals one-half the arc XY, and this are depends only on the length of the chord XY. This ‘completes the proof. ‘One might ask: How in the world did anyone ever think to extend XC in this way? This is precisely the step that makes the argument so pretty, and itis indeed a very difficult step to motivate. About all that can be said is that the use of auxiliary lines and ares (often found by reflection, extension, cr rotation) is a common practice in geometry. Just the awareness of this fact will add to the possible approaches in a given problem, ‘Another interesting approach to this problem is to coordinatize the points and to proceed analytically. To show that the shape of the triangle is, independent of the position of the chord, it suffices to show that the height-to-base ratio, MN'/CD, is constant, Let © denote the midpoint of AB, and let @ = 2 YOB, ICis clear that the entire configuration is completely determined by @ (Figure 1.3). Let a= ZXOY. Using this notation, €D = c0s8 ~ cos(0 + a), sind + sin(@ + a) —_{ MN = and the height-base ratio is sin# + sin(@ + «) eos — cos(+ ah) * is not immediately clear that this quantity is independent of @; this is the content of 1.8.1 and 646.7. Fo) = 0<8 [*] = 4(No. of lattice points in the interior of ABCD ) ms (a= =) or. 1.24 (The handshake problem). Mr. and Mrs. Adams recently attended a party at which thete were three other couples, Various handshakes took place, No one shook hands with his/her own spouse, no one shook hands with the same person twice, and of course, n0 onc shook his/her own hand. ‘After all the handshaking was finished, Mr. Adams asked each person, including his wife, how many hands he or she had shaken, To his surprise, cach gave a different answer. How many hands did Mrs. Adams shake? Solution. Although a diagram is not essemtial to the solution, it is helpful to view the data graphically in the following fashion. Represent the eight individuals by the eight dots as shown in Figure Now the answers to Mr. Adams’ query must have been the numbers 0,1,2,3,4,5,6. Therefore, one of the individuals, say 4, has shaken hands with six others, say B,C, D, E, F,G. Indicate this on the graph by drawing line segments from A to these points, as in Figure 1.8. From this diagram, we see that H must be that person who has shaken no one’s hand. Furthermore, 4 and H must be spouses, because 4 has ‘shaken hands with six others, not counting his/her own spouse. 12, Draw a Figure 13 A Figure 1.10, By supposition, one of B,C,D,£,F,G, has shaken five hands. By relabeling if necessary we may assume this person is B. Also, we may assume without loss of generality that the five with whom B has shaken bands are labeled A,C,D,£,F. This is shown in Figure 1.9. From this sketch we easily sce that G is the only person who could have answered “one”, and B and G must be spouses, Again, as before, by relabeling the points C,D,& if necessary, we may assume that C shook four hands and shat they belonged t0 4, 8,D,E. The corresponding diagram is given in Figure 1.10, Using the same reasoning as, above, F and C ate spouses, and consequently, D and £ are spouses. Each of D and £ has shaken hands with three others. Since Mr, Adams did not receive two “three” answers, D and E must correspond to Mr. and Mrs. Adams; that is to say, Mrs. Adams shook hands with three others. Problems 1.25, Two poles, with heights @ and b, are a distance d apart (along level wound). A guy wire stfetches from the {op of each of them to some point P fn the ground between them. Where should P be located to minimize the total length of the wire? (Mint: Let the poles be erected at points C and D, and their tops be labeled 4 and 2, respectively. We wish to minimize AP + PB. Avgment this disgram by reflecting it in the base line CD. 4 1. Heuristics Suppose B reflects to 8” (PB = PB‘). Now the problem is: Where should P be located to minimize AP + PB”) 1.2.6. Let ABC be an acute-angled triangle, and let D be on the interior of the segment AB, Locate points £ on AC and F on CB such that the inscribed triangle DEF will have minimum perimeter. (Hint; Reflect D in line AC to a point D’; reflect D in CB to a point D” and consider the line segment D'D",) 1.2.7, A rectangular room measures 30 feet in length and 12 feet in height, and the ends are 12 feet in width. A fly, with a broken wing, rests at a point ‘one foot down from the ceiling at the middle of one end. A smudge of food is located one foot up from the floor at the middle of the other end. The fly ‘has just enough energy to walk 40 feet. Show that there is a path along which the fly can walk that will enable it to get to the food. 1.28, Equilaterai triangles ABP and ACQ are constructed externally om the sides 4B and AC of triangle ABC. Prove that CP = BQ. (Hint: For a nice solution, rotate the plane of the triangle 60° about the point A, in a direction which takes B in the direction of C. What happens to the line segment CP?) 1.29, Let a and b be given positive real numbers with a < b. If two points are selected at random from a straight line segment of length b, what is the probability that the distance between them is at least a? (Hint: Let x and y denote the randomly chosen numbers from the interval [0,6], and consider these independent random variables on two separate axes. What area corresponds to |x — y| > a) 1.2.10. Give a geometric interpretation to the following problem. Let f be differentiable with f° continuous on [2,6]. Show that if there is a number ¢ in (a,b) such that f'(c) = 0, then we can find a number d in (a,b) such that fed) ~ fea) boa 12.11. Let a and b be real numbers, a O and ‘n> 0, (The latter number corresponds to the center of gravity of a system of two masses—one, of mass m, located at a, and the other, of mass m, located at b) 1.2.12, Use the graph of y = sinx to show the following. Given triangle ABC, (0) SDBESNC & gin BEC, f@= (0) Bbq tin + sinc < sin A B+ HAC) > 0,0 >0 13, Formulate an Equivalent Probie Is 1.2.13, Use a diagram (a rectangular array (a,2,)) to show that @) 3 Sag=F Sao, Bofo'? foizo 0) Be Sag. © (34) -3, Sae-23 Sag- Se re) Ba me Additional Examples Most of the problems in Chaper 8 (Geometry); also 1.3.11, 1.92, 11.3, 2.1.3, 25.5, 26.11, $12, 62.2, 6.4.1, 663, 681, 7.1.14, 7.4.19, 7.6.1, 81.1. 1.3. Formulate an Equivalent. Problem ‘The message of the preceding section is that the first step in problem solving is 10 gather data, 10 explore, to understand, to relate, to conjecture, to analyze, But what happens when it is not possible 10 do this in @ ‘meaningful way, either because the computations become to0 complicated for because the problem simply admits no special cases that shed any insight? In this section we will consider some problems of this type. The ‘recommendation of this section is to try to reformulate the problem into an equivalent but simpler form. The appeal is to one’s imagination and creativity. Some standard reformulation techniques involve algebraic or igonometric manipulation, substitution or change of variable, use of ‘one-to-one correspondence, and reinterpretation in the language of another subject (algebra, geometry, analysis, combinatorics, etc.) 13.1, Find a general formula for the,nth derivation of f(x) = 1/(1~ 2?) Solution. A common simplifying step when working with rational functions is to write the function as a sum of partial fractions. In this case, feo=a[ pty t Tes 16 1, Heres ‘and in this form it is easy to show that py aon ata 2| asa 13.2, Find all solutions of x44 x74 x7 +x +1=0. Solution. This equation can be solved by dividing by x7, then substituting yr x+1/x, and then applying the quadratic formula. Thus, we have 244 L x4 beet pt lag, (er2eb)s(ert}ea-ae (erdfelertyorne ‘The roots of this equation are ait ae 8, na temas 0 determine by soving he equations stlay and xttoy, hich ar equate tayxtl=0 and P-yxt1=0. The four roots found by solving these are -148 ,, lors ee +8 _ Vins 2s => 1-8 4 MIO 25 2 _ Yio- 25 a Another approach to this problem is to multiply cach side of the original equation by x = 1. Since (x — 1x4 + 2? 4 aF+ x+ 1) =x? = 1, an equiv x 1.3. Formolate an Equvaleat Problem 0 alent problem is to find all x (other than x = 1) which satisfy x* = 1, These are the Five fifth roots of unity, given by x = c0sir + ising, xy = cos $x + isindr, xy cos$a + isin$n, xy = costa + isin, As a by-product of having worked this problem two different ways, we see that det ininte 2 ES, 0+ OT conga + sings = EE 4 YAS Equating real and imaginary parts yields “128 nee Yio+35 cos 72° = 7 (Similar formulas can be found for x2, x3, and %,.) 13,3, P is a point inside a given triangle ABC; D, E,F are the feet of the perpendicular from P to the lines BC, CA, AB, respectively. Find all P for which Bl, A, AB PD * PE* PF is minimal. Solution, Denote the lengtbs of BC, AC, AB by a,b,c, respectively, and PD, PE, PF by p,qur, respectively (see Figute 1.11), We wish to minimize a/p+b/q+e/r. Figure 1.1, 18 1. Heoriti Notice that ‘Area ABC = Area ABCP + Area ACAP + Area AABP ~ fap + bbq + her grater 2 ‘Thos, ap + bq + cr is a constant, independent of the placement of P. ‘Therefore, instead of minimizing a/p+b/q+c/r, we will minimize (ap + bq + crka/p + b/q+c/n). (This step will appear more natural after a study of inequalities with constraints taken up in Section 7.3.) We have a en(S bad errorven(te des) wats he crt ab( 244) 4 bef 242) +ac( 244 sPreedlSs states a) re s+ 5) > abt tel + ab + 2be + 2ae =(atbtey. The inequality in the second step follows from the fact that for any two positive numbers x and y we have x/p +y/x > 2, with equality if and only if xy, As result of this fact, (ap + bg + crXa/p + 6/q + e/r) will tain its shinimum value (a+ 6+ ¢) when, and only when, p= q=r. Equivalently, a/p + b/q + ¢/7 attains a minimum value when P is located at the incenter of the triangle. 1.3.4, Prove that if m and n are positive integers and 1 < k < m, then Ss ynyy me ” ZTE") ‘Solution. The staterient of the problem constitutes one of the fundamental identities involving binomial coefficients, On the left side is a sum of products of binomial coefficients. Obviously, a direct substitution of facto- Fials for binomial coefficients provides no insight. ‘Quite often, finite series (especially those which involve binomial coeffi- cients) can be summed combinatorially. To understand what is meant here, transform the series problem into @ counting problem in the following manner. Let S= A U B, where A is a set with n elements and B is set, disjoint from 4, with m elements. We will count, in two different ways, the number of (distinct) A-subsets of 5, On the one hand, this number is ("2"). On the other hand, the number of k-subscts of S with exactly 7 elements

You might also like