AMS/MAA TEXTBOOKS VOL 41 Journey into Discrete Mathematics Owen D. Byer, Deirdre L. Smeltzer, and Kenneth L. Wantz CommitteeonBooks JenniferJ.Quinn,Chair MAATextbooksEditorialBoard StanleyE.Seltzer,Editor WilliamRobertGreen,Co-Editor BelaBajnok SuzanneLynneLarson JeffreyL.Stuart MatthiasBeck JohnLorch RonD.Taylor,Jr. HeatherAnnDye MichaelJ.McAsey ElizabethThoren CharlesR.Hampton VirginiaNoonburg RuthVanderpool 2010MathematicsSubjectClassification.Primary97K20,97K30,97F60,97N70,97E30. Foradditionalinformationandupdatesonthisbook,visit www.ams.org/bookpages/text-41 LibraryofCongressCataloging-in-PublicationData Names:Byer,Owen,author.|Smeltzer,DeirdreL.,author.|Wantz,KennethL.,1965-author. Title:Journeyintodiscretemathematics/OwenD.Byer,DeirdreL.Smeltzer,KennethL.Wantz. Description: Providence,RhodeIsland: MAAPress,animprintoftheAmericanMathematicalSociety, [2018]|Series:AMS/MAAtextbooks;volume41|Includesbibliographicalreferencesandindex. Identifiers:LCCN2018023584|ISBN9781470446963(alk.paper) Subjects: LCSH:Settheory. |Numbertheory. |Mathematicalanalysis. |Combinatorialanalysis. |AMS: Mathematicseducation–Combinatorics,graphtheory,probabilitytheory,statistics–Combinatorics. msc|Mathematicseducation–Combinatorics,graphtheory,probabilitytheory,statistics–Graphthe- ory. msc|Mathematicseducation–Arithmetic,numbertheory–Numbertheory. msc|Mathematics education–Numericalmathematics–Discretemathematics. msc|Mathematicseducation–Founda- tionsofmathematics–Logic.msc Classification:LCCQA248.B96572018|DDC511/.1–dc23 LCrecordavailableathttps://lccn.loc.gov/2018023584 Colorgraphicpolicy. Anygraphicscreatedincolorwillberenderedingrayscalefortheprintedversion unlesscolorprintingisauthorizedbythePublisher. Ingeneral,colorgraphicswillappearincolorinthe onlineversion. Copyingandreprinting. Individualreadersofthispublication,andnonprofitlibrariesactingforthem, arepermittedtomakefairuseofthematerial,suchastocopyselectpagesforuseinteachingorresearch. Permissionisgrantedtoquotebriefpassagesfromthispublicationinreviews,providedthecustomaryac- knowledgmentofthesourceisgiven. Republication,systematiccopying,ormultiplereproductionofanymaterialinthispublicationispermit- tedonlyunderlicensefromtheAmericanMathematicalSociety.Requestsforpermissiontoreuseportions ofAMSpublicationcontentarehandledbytheCopyrightClearanceCenter. Formoreinformation,please visitwww.ams.org/publications/pubpermissions. Sendrequestsfortranslationrightsandlicensedreprintstoreprint-permission@ams.org. ©2018bytheAmericanMathematicalSociety.Allrightsreserved. TheAmericanMathematicalSocietyretainsallrights exceptthosegrantedtotheUnitedStatesGovernment. PrintedintheUnitedStatesofAmerica. ⃝1Thepaperusedinthisbookisacid-freeandfallswithintheguidelines establishedtoensurepermanenceanddurability. VisittheAMShomepageathttps://www.ams.org/ 10987654321 232221201918 Contents Preface vii WhatIsDiscreteMathematics? vii GoalsoftheBook vii FeaturesoftheBook viii CourseOutline ix Acknowledgments xi 1 ConvinceMe! 1 1.1 OpeningProblems 2 1.2 Solutions 4 2 Mini-Theories 9 2.1 Introduction 9 2.2 DivisibilityofIntegers 14 2.3 Matrices 22 3 LogicandSets 31 3.1 Propositions 31 3.2 Sets 33 3.3 LogicalOperatorsandTruthTables 38 3.4 OperationsonSets 44 3.5 TruthValuesofCompoundPropositions 51 3.6 SetIdentities 54 3.7 InfiniteSetsandParadoxes 58 4 LogicandProof 67 4.1 LogicalEquivalences 67 4.2 Predicates 73 4.3 NestedQuantifiers 77 4.4 RulesofInference 83 4.5 MethodsofProof 91 5 RelationsandFunctions 101 5.1 Relations 101 5.2 PropertiesofRelationsonaSet 106 5.3 Functions 113 5.4 Sequences 123 iii iv Contents 6 Induction 133 6.1 InductiveandDeductiveThinking 133 6.2 Well-OrderingPrinciple 135 6.3 MethodofMathematicalInduction 137 6.4 StrongInduction 147 6.5 ProofoftheDivisionTheorem 151 7 NumberTheory 155 7.1 Primes 155 7.2 TheEuclideanAlgorithm 159 7.3 LinearDiophantineEquations 165 7.4 Congruences 169 7.5 Applications 176 7.6 AdditionalProblems 178 8 Counting 183 8.1 WhatIsCounting? 183 8.2 CountingTechniques 184 8.3 PermutationsandCombinations 193 8.4 TheBinomialTheorem 203 8.5 AdditionalProblems 207 9 GraphTheory 211 9.1 TheLanguageofGraphs 212 9.2 TraversingEdgesandVisitingVertices 221 9.3 VertexColorings 230 9.4 Trees 238 9.5 ProofsofEuler’sandOre’sTheorems 249 10 InvariantsandMonovariants 253 10.1 Invariants 253 10.2 Monovariants 259 11 TopicsinCounting 267 11.1 Inclusion-Exclusion 267 11.2 ThePigeonholePrinciple 274 11.3 MultinomialCoefficients 278 11.4 CombinatorialIdentities 282 11.5 OccupancyProblems 286 12 TopicsinNumberTheory 299 12.1 MoreonPrimes 299 12.2 IntegersinOtherBases 303 12.3 MoreonCongruences 311 12.4 NonlinearDiophantineEquations 318 12.5 Cryptography: Rabin’sMethod 319 Contents v 13 TopicsinGraphTheory 327 13.1 PlanarGraphs 327 13.2 ChromaticPolynomials 331 13.3 SpanningTreeAlgorithms 337 13.4 PathandCircuitAlgorithms 342 Hints 355 ListofNames 381 Bibliography 383 Index 385 Preface What Is Discrete Mathematics? Theworddiscreteinmathematicsisincontrasttothewordcontinuous. Forexample, thesetofintegersisdiscrete,whilethesetofrealnumbersiscontinuous. Thus,dis- cretemathematicsdescribesacollectionofbranchesofmathematicswiththecommon characteristicthattheyfocusonthestudyofthingsconsistingofseparate,irreducible, oftenfiniteparts. Althoughlargelyneglectedintypicalprecollegemathematicscur- ricula,discretemathematicsisessentialfordevelopinglogicandproblem-solvingabil- ities. Questionslocatedwithintherealmofdiscretemathematicsnaturallyinvitecre- ativityandinnovativethinkingthatgobeyondformulas. Furthermore,thecultivation oflogicalthinkingformsanecessaryfoundationforproof-writing. Forthesereasons, discretemathematicsiscriticalforundergraduatestudyofbothmathematicsandcom- puterscience. Goals of the Book Simplystated,thegoalofJourneyintoDiscreteMathematicsistonurturethedevelop- mentofskillsneededtolearnanddomathematics. Theseskillsincludetheabilityto read,write,andappreciateagoodmathematicalproof,aswellasabasicfluencywith coremathematicaltopicssuchassets,relationsandfunctions,graphtheory,andnum- ber theory. The content and the corresponding requisite mathematical thinking are appropriate for students in computer science and other problem-solving disciplines, butthecontentpresentationandthenatureoftheproblemsetsreinforcetheprimary goaloftrainingmathematicians. Throughoutthebook,weemphasizethelanguageof mathematicsandtheessentialsofproof-writing,andweunderscorethattheprocessis veryimportantinmathematics. Entry-leveldiscretemathematicsservesasanexcellentgatewaytoupper-levelmath- ematics by priming students’ minds for upper-level concepts. Journey into Discrete Mathematicsisdesignedforuseinthefirstnoncalculuscourseofamathematicsma- jor, employing a writing style that models a high degree of mathematical accuracy whilemaintainingaccessibilityforearlycollegestudents. Forexample,thetreatment ofinclusion-exclusionprovidesbothinformalandtechnicallypreciseexplanations.Ul- timately,thegoalbehindthisapproachiscommunication:wewanttomodelandteach studentstocommunicatebothaccuratelyandclearly. vii viii Preface JourneyintoDiscreteMathematicsutilizesproblemsandexamplestolaythefoun- dationforconceptstobeencounteredinfuturemathematicscourses.Forexample,the chapteronrelationsandfunctionsintroducesstudentstodefinitionssuchasone-to- oneandonto;severalproblemsinChapter4guidestudentsthroughdefinitionsofcon- tinuityusingnestedquantifiers;thetreatmentofgreatestcommondivisorforeshadows findingtheGCDofpolynomialfunctions;thebinomialandmultinomialtheoremsare presented as tools for combinatorial counting; and Euler’s totient function and Fer- mat’sLittleTheoremareimportantnumber-theoreticconceptsthatstudentswillsee againinanabstractalgebracourse. Thehomeworkquestionsaredividedintosections accordingtodifficulty,spanningthegamutfromroutinetoquitechallenging.Thefirst sectiongenerallyincludesexercisesthataremoreroutineorcomputational,meantto givestudentsachancetopracticegiventechniques,whilethelattersectionsgenerally consistofproblemsthatrequirecreativity,synthesisofmultipleconcepts,orproofs. This book takes the time to describe the origins of important discrete math top- icsaswellastheconnectionsbetweenconcepts. Thetreatmentofmatricesreferences ArthurCayley’sfirstuseofmatrices;theintroductionofFibonaccinumbersisplaced withinhistoricalcontext; theworkoninductivethinkingandproofbyinductionex- hibitscareformakingconnectionswithdeductivethinking,theWell-OrderingPrinci- ple,andothermathematicalconcepts. Inspirationalquotesthroughoutthebookand theincorporationofthefirstnamesofmathematiciansinexamplesandexercises(with acorrespondingsummarylistprovidingabriefbiographyforeachonementioned)con- tributetofamiliarizingstudentswiththenamesofkeyfigureswithindiscretemathe- matics. Features of the Book ConvinceMeChapter. This opening chapter contains a selection of interesting, non- standard problems of varying degrees of difficulty. Readers are invited to think cre- ativelyandarguepersuasivelyastheyworktofindsolutions. Thisprocesscultivates anunderstandingoftheimportanceofmakingagoodmathematicalargument,while setting the tone for the problem-solving nature of the book. Moreover, many of the solutionsinthischapterforeshadowthemathematicaltechniquesandtheoremsthat willbeencounteredlaterinthebook. HookProblems. InthemanneroftheConvinceMeproblems,eachchapterbegins withanintriguingandchallengingproblemintendedtocapturethereader’sinterest. Eachhookproblemcanbesolvedusingtechniquestobedevelopedinthechapterand usuallyreappearslaterinthechapter,eitherasanexampleorasahomeworkproblem. PresentationofLogic.Chapters3and4ofthebookcombinethetopicsofsets,logic, andproof-writinginadistinctiveway. Thisapproachhelpstohighlightthehighlevel ofcongruitybetweenconceptssuchasDeMorgan’sLawsforsetsandlogic,member- shiptablesandtruthtables,logicaloperatorsandsetoperators. Thechapteronlogic andproof-writingappearsearlyinthebooktohelpstudentsbridgethegapbetween intuitivethinkingandtheformalpresentationofanargument,bothofwhicharenec- essaryinmathematics. FirstThoughtsandFurtherThoughts. Solutionstomanyexamplesinthebookare preceded by “First Thoughts”, describing the initial thought process that one might engageinwhenfirstconsideringanewproblem. Thisisintendedtobebothhelpful CourseOutline ix andreassuringtostudentswhomightbeintimidatedbyseeingfinalpolishedproofs andassumingthat“real”mathematicianscanproducetheseimmediately,withoutin- termediarystrugglesorfailedattempts. FirstThoughtshelptrainstudentsintheways that mathematicians actually operate. Similarly, “Further Thoughts” often follow a solutioninordertoprovideadditionalinsightabout,alternativeapproachesto,orex- tensionsofthegivensolution;onceagain,thegoalistocultivateaspiritofdoingmath- ematics. AdvancedTopicChapters.Severalcoretopics(counting,numbertheory,andgraph theory)areaddressedtwiceinthisbook:firstinanintroductorychaptercoveringstan- dardcontentandlaterinachapterwithextendedoptional(often,butnotalways,more advanced)material. Thisprovidesinstructorswithflexibilitytocustomizethecourse, dependingontheirparticulargoals,orexpandbeyondatypicalfirstcourseindiscrete mathematics. Course Outline Thisbookisdesignedtobeusedasastand-alonetextforathree-creditorfour-credit discretemathematicscourseforaveragetoaboveaveragemathmajorswhoarelearn- ing to write proofs; however, since there is more material in this book than can be coveredinasinglesemester,instructorswillhavetomakesomechoices. Forstudents whohavealreadyhadanintroduction-to-proofscourse,selectportionsofthefirstsix chaptersofthebookcanbecoveredratherquickly, andthelasthalfofthebookcan serveasamaintextforajunior-levelcourseincombinatorics. Ifthisbookissupple- mented with a few extra topics (such as probability, solving recurrence relations, or finite-statemachines), thenthereisenoughmaterialforatwo-semestersequencein discretemathematics. Withthatgoalinmind,wesuggestonedesignforsuchathree-creditcourse. The secondcolumninTable0.1onpagexliststhecoresectionswebelieveshouldbecov- ered.Weestimatethatthecoresectionscanbecoveredinaboutthirty-fourfifty-minute lectures. Theremainingclassperiodscouldbeusedforreviewdays,testingdays,and optional sections from the third column. The first column of the table lists sections andchapterscontainingmaterialthatisessentialforstudentstoknowbeforecover- ingcorrespondingsectionsofthemiddletwocolumns. Themiddlecolumnscontain materialthatisusedinsectionsandchapterslistedinthefourthcolumn,thoughthey maynotbeabsoluteprerequisites. Forexample,althoughmatrices(firstaddressedin Section2.3)alsoappearinChapter9(GraphTheory),oneneednotstudySection2.3 inordertobeabletounderstandtheessentialcomponentsofChapter9.