THE ART AND CRAFTOF PROBLEM SOLVINGSecond EditionPaul ZeitzUniversity of San Francisco i zzIIB.e:ENTENNIAL1 807II z WILEY 2007BICENTENNIALz! rJohn Wiley & Sons, Inc.

Angela BattleJennifer BattistaDaniel GraceKen SantorAmy SellMichael St. MartineSteve Casimiro/The Image Bank/GettyImages, Inc.ACQUISITIONS EDITORPROJECT EDITOREDITORIAL ASSISTANTSENIOR PRODUCTION EDITORMARKETING MANAGERCOVER DESIGNERCOVER PHOTOThis book was set in LaTeX by the author and printed and bound by Malloy, Inc .The cover was printed by Phoenix Color .This book is printed on acid free paper .00Copyright 2007 John Wiley & Sons, Inc. All rights reserved .No part of this publication may be reproduced, stored in a retrieval system or transmitted inany form or by any means, electronic, mechanical, photocopying, recording, scanning orotherwise, except as permitted under Sections 1 07 or 1 08 of the 1 976 United States CopyrightAct, without either the prior written permission of the Publisher, or authorization throughpayment of the appropriate per-copy fee to the Copyright Clearance Center, Inc . 222Rosewood Drive, Danvers, MA 0 1 923, (978)750-8400, fax (978)646-8600 . Requests to thePublisher for permission should be addressed to the Permissions Department, John Wiley &Sons, Inc., I I I River Street, Hoboken, NJ 07030-5774, (20 1 )748-60 1 1 , fax (20 1 )748-6008 .To order books or for customer service please, call 1 -800-CALL WILEY (225-5945) .ISBN- I OISBN- 1 30-47 1 -7890 1 - 1978-0-47 1 -7890 1 -7Printed in the United States of America10 9 8 7 6 5 4 3 2 I

To My Family

The explorer is the person who is lost.-Tim Cahill, Jaguars Ripped My FleshWhen detectives speak of the moment that a crime becomes theirs toinvestigate, they speak of "catching a case," and once caught, a case islike a cold: it clouds and consumes the catcher's mind until, like a fever,it breaks; or, if it remains unsolved, it is passed on like a contagion,from one detective to another, without ever entirely releasing its holdon those who catch it along the way.-Philip Gourevitch, A Cold Case

Preface to the Second Ed itionThis new edition of The Art and Craft of Problem Solving is an expanded, and, I hope,improved version of the original work. There are several changes, including: A new chapter on geometry. It is long-as many pages as the combinatoricsand number theory chapters combined-but it is merely an introduction to thesubject. Experts are bound to be dissatisfied with the chapter's pace (slow, es pecially at the start) and missing topics (solid geometry, directed lengths andangles, Desargues 's theorem, the 9-point circle). But this chapter is for begin ners; hence its title, "Geometry for Americans." I hope that it gives the noviceproblem solver the confidence to investigate geometry problems as agressivelyas he or she might tackle discrete math questions.An expansion to the calculus chapter, with many new problems.More problems, especially "easy" ones, in several other chapters.To accommodate the new material and keep the length under control, the problems arein a two-column format with a smaller font. But don 't let this smaller size fool youinto thinking that the problems are less important than the rest of the book. As with thefirst edition, the problems are the heart of the book. The serious reader should, at thevery least, read each problem statement, and attempt as many as possible. To facilitatethis, I have expanded the number of problems discussed in the Hints appendix, whichnow can be found online at www . wi ley . com/ c o l l e ge / z e i t z .I am still indebted to the people that I thanked in the preface to the first edition. Inaddition, I'd like to thank the following people. Jennifer Battista and Ken Santor at Wiley expertly guided me through the revi sion process, never once losing patience with my procrastination.Brian Borchers, Joyce Cutler, Julie Levandosky, Ken Monks, Deborah Moore Russo, James Stein, and Draga Vidakovic carefully reviewed the manuscript,found many errors, and made numerous important suggestions.At the University of San Francisco, where I have worked since 1 992, DeanJennifer Turpin and Associate Dean Brandon Brown have generously supportedmy extracurricular activities, including approval of a sabbatical leave during the2005--06 academic year which made this project possible.S ince 1 997, my understanding of problem solving has been enriched by mywork with a number of local math circles and contests. The MathematicalSciences Research Institute (MSRI) has sponsored much of this activity, andI am particularly indebted to MSRI officers Hugo Rossi, David Eisenbud, JimSotiros, and Joe Buhler. Others who have helped me tremendously include TomRike, Sam Vandervelde, Mark Saul, Tatiana Shubin, Tom Davis, Josh Zucker,and especially, Zvezdelina Stankova.ix

xAnd last but not least, I 'd like to continue my contrition from the first edition, andask my wife and two children to forgive me for my sleep-deprived inattentiveness. Idedicate this book, with love, to them.Paul ZeitzSan Francisco, June 2006Preface to the Fi rst Ed itionWhy This Book?This is a book about mathematical problem solving for college-level novices. By thisI mean bright people who know some mathematics (ideally, at least some calculus),who enjoy mathematics, who have at least a vague notion of proof, but who have spentmost of their time doing exercises rather than problems.An exercise is a question that tests the student 's mastery of a narrowly focusedtechnique, usually one that was recently "covered." Exercises may be hard or easy, butthey are never puzzling, for it is always immediately clear how to proceed. Gettingthe solution may involve hairy technical work, but the path towards solution is alwaysapparent. In contrast, a problem is a question that cannot be answered immediately.Problems are often open-ended, paradoxical, and sometimes unsolvable, and requireinvestigation before one can come close to a solution. Problems and problem solvingare at the heart of mathematics. Research mathematicians do nothing but open-endedproblem solving. In industry, being able to solve a poorly defined problem is muchmore important to an employer than being able to, say, invert a matrix. A computercan do the latter, but not the former.A good problem solver is not just more employable. Someone who learns how tosolve mathematical problems enters the mainstream culture of mathematics; he or shedevelops great confidence and can inspire others. Best of all, problem solvers havefun; the adept problem solver knows how to play with mathematics, and understandsand appreciates beautiful mathematics.An analogy: The average (non-problem-solver) math student is like someone whogoes to a gym three times a week to do lots of repetitions with low weights on variousexercise machines. In contrast, the problem solver goes on a long, hard backpackingtrip. Both people get stronger. The problem solver gets hot, cold, wet, tired, andhungry. The problem solver gets lost, and has to find his or her way. The problemsolver gets blisters. The problem solver climbs to the top of mountains, sees hithertoundreamed of vistas. The problem solver arrives at places of amazing beauty, andexperiences ecstasy that is amplified by the effort expended to get there. When theproblem solver returns home, he or she is energized by the adventure, and cannot stopgushing about the wonderful experience. Meanwhile, the gym rat has gotten steadilystronger, but has not had much fun, and has little to share with others.While the majority of American math students are not problem solvers, there doesexist an elite problem solving culture. Its members were raised with math clubs, andoften participated in math contests, and learned the important "folklore" problems and

xiideas that most mathematicians take for granted. This culture is prevalent in parts ofEastern Europe and exists in small pockets in the United States. I grew up in New YorkCity and attended Stuyvesant High School, where I was captain of the math team, andconsequently had a problem solver's education. I was and am deeply involved withproblem solving contests. In high school, I was a member of the first USA team toparticipate in the International Mathematical Olympiad (lMO) and twenty years later,as a college professor, have coached several of the most recent IMO teams, includingone which in 1 994 achieved the only perfect performance in the history of the IMO.But most people don 't grow up in this problem solving culture. My experiencesas a high school and college teacher, mostly with students who did not grow up asproblem solvers, have convinced me that problem solving is something that is easyfor any bright math student to learn. As a missionary for the problem solving culture,The Art and Craft of Problem Solving is a first approximation of my attempt to spreadthe gospel. I decided to write this book because I could not find any suitable text thatworked for my students at the University of San Francisco. There are many nice bookswith lots of good mathematics out there, but I have found that mathematics itself is notenough. The Art and Craft of Problem Solving is guided by several principles: Problem solving can be taught and can be learned.Success at solving problems is crucially dependent on psychological factors.Attributes like confidence, concentration, and courage are vitally important.No-holds-barred investigation is at least as important as rigorous argument.The non-psychological aspects of problem solving are a mix of strategic prin ciples, more focused tactical approaches, and narrowly defined technical tools.Knowledge of folklore (for example, the pigeonhole principle or Conway 'sChecker problem) is as important as mastery of technical tools.Read i n g This BookConsequently, although this book is organized like a standard math textbook, its toneis much less formal: it tries to play the role of a friendly coach, teaching not just byexposition, but by exhortation, example, and challenge. There are few prerequisites only a smattering of calculus is assumed-and while my target audience is collegemath majors, the book is certainly accessible to advanced high school students and topeople reading on their own, especially teachers (at any level).The book is divided into two parts. Part I is an overview of problem-solvingmethodology, and is the core of the book. Part II contains four chapters that can be readindependently of one another and outline algebra, combinatorics, number theory, andcalculus from the problem solver's point of view. I In order to keep the book's lengthmanageable, there is no geometry chapter. Geometric ideas are diffused throughoutthe book, and concentrated in a few places (for example, Section 4.2). Nevertheless,I To conserve pages, the second edition no longer uses formal "Part I" and "Part II" labels. Nevertheless, thebook has the same logical structure, with an added chapter on geometry. For more information about how to readthe book, see Section1.4 .

xiithe book is a bit light on geometry. Luckily, a number of great geometry books havealready been written. At the elementary level, Geometry Revisited [6] and Geometryand the Imagination [2 1 ] have no equals.The structure of each section within each chapter is simple: exposition, examples,and problems-lots and lots-some easy, some hard, some very hard. The purpose ofthe book is to teach problem solving, and this can only be accomplished by grapplingwith many problems, solving some and learning from others that not every problem ismeant to be solved, and that any time spent thinking honestly about a problem is timewell spent.My goal is that reading this book and working on some of its 660 problems shouldbe like the backpacking trip described above. The reader will definitely get lost forsome of the time, and will get very, very sore. But at the conclusion of the trip, thereader will be toughened and happy and ready for more adventures.And he or she will have learned a lot about mathematics-not a specific branch ofmathematics, but mathematics, pure and simple. Indeed, a recurring theme throughoutthe book is the unity of mathematics. Many of the specific problem solving meth ods involve the idea of recasting from one branch of math to another; for example, ageometric interpretation of an algebraic inequality.Teaching With Th i s BookIn a one-semester course, virtually all of Part I should be studied, although not all ofit will be mastered. In addition, the instructor can choose selected sections from PartII. For example, a course at the freshman or sophomore level might concentrate onChapters 1 -6, while more advanced classes would omit much of Chapter 5 (except thelast section) and Chapter 6, concentrating instead on Chapters 7 and 8.This book is aimed a t beginning students, and I don 't assume that the instructor i sexpert, either. The Instructor's Resource Manual contains solution sketches t o most ofthe problems as well as some ideas about how to teach a problem solving course. Formore information, please visit www . wi ley . com/ c o l lege / z eit z .AcknowledgmentsDeborah Hughes Hallet has been the guardian angel of my career for nearly twentyyears. Without her kindness and encouragement, this book would not exist, nor wouldI be a teacher of mathematics. l owe it to you, Deb. Thanks!I have had the good fortune to work at the University of San Francisco, where Iam surrounded by friendly and supportive colleagues and staff members, students wholove learning, and administrators who strive to help the faculty. In particular, I 'd liketo single out a few people for heartfelt thanks: My dean, Stanley Nel, has helped me generously in concrete ways, with com puter upgrades and travel funding. But more importantly, he has taken an activeinterest in my work from the very beginning. His enthusiasm and the knowl edge that he supports my efforts have helped keep me going for