W.D. Wallis Mathematics in the Real World W.D. Wallis Mathematics in the Real World W.D.Wallis DepartmentofMathematics SouthernIllinoisUniversity Carbondale,IL,USA ISBN978-1-4614-8528-5 ISBN978-1-4614-8529-2(eBook) DOI10.1007/978-1-4614-8529-2 SpringerNewYorkHeidelbergDordrechtLondon LibraryofCongressControlNumber:2013945165 MathematicsSubjectClassification(2010):05-01,15-01,60-01,62-01,91B12,97-01 ©SpringerScience+BusinessMediaNewYork2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.birkhauser-science.com) Thisbookisdedicatedto thememoryof RolfRees andTom Porter,two colleagues who leftusfar toosoon. Preface Inrecentyears,therehasbeenanoticeableincreaseinthenumberofcollegecourses designedtointroducemathematicstonon-mathstudents.Iamnottalkingaboutthe sort of mathematics studied at school, a glorified version of arithmetic with sole lettersthrownintorepresentnumbers,butrealmathematics—thestudyofpatterns andstructures(andyes,sometimesnumbersareinvolved)thatariseinoureveryday lives. Thisbookisdesignedasatextforsuchacourse,aone-semestercoursedesigned forstudentswithaminimalbackgroundinmathematics. OutlineofTopics The first two chapters discuss the basics of numbers and set theory. Chapter 1 (Numbers and Sets) introducesthe idea of a set and a subset (a part of a set); the setsofnumbersthatweusearediscussed.Muchofthismaterialwillbefamiliarto the reader, but you may see these topics differently after you see how the ideas are connected. We then introduce the idea of a base for numbers; we normally usebase10,butotherbasesareusefulfordealingwithcomputers.Therestofthe chapterisaboutrepresentingandusingnumericaldata:summation,somenotation forsummations,and somewaysof combiningsets are introduced,Venndiagrams arediscussed,andfinallywelookatarraysofnumbersanddefinematrices. Counting is covered in Chap. 2 (Counting). The concept of an event, a col- lection of possible outcomes, is introduced. Summations, which were a topic in Chap. 1, are studied further. We also distinguish between countingthe numberof selectionsorcombinations—subsetsofagivensize—andcountingarrangementsor permutations—subsetswheretheorderoftheelementsisimportant. Counting leads naturally to probability theory. In Chap. 3 (Probability) we introducethebasicideasofprobability.Randomnessandrandomeventsaredefined. A number of examples involving dice and playing cards are included. In order to discuss compound events, tree diagrams (similar to family trees, which we’ll vii viii Preface mention later) are introduced. We go through two examples where probabilities aredifferentfromwhatmanypeopleexpect—thebirthdayproblemandtheMonty Hall problem. Finally, the more mathematical concept of a probability model is introduced. The next two chapters deal with statistics, and in particular those aspects (sampling, polls, predictions) that we often see in everyday life. As a first step toward describing statistics, Chap. 4 (Data: Distributions) examines the way in which numerical data about our world is collected and described. The ideas of a populationandtakinga samplefromthatpopulationareintroduced,togetherwith ways of displaying this information—the dotplot, histogram, and boxplot—and parameters that describe the information, such as means, medians, and quartiles. Probability distributions are introduced, as a way of representing the probability modelofaphenomenon;inparticular,welookatthenormaldistribution. Chapter 5 (Sampling: Polls, Experiments) looks at how statistics impinges on ourworld:estimatingnumericalpropertiesofoursocietyanddecidinghowreliable are those estimates. A sample is the group we examine to study a property (such as family income and height). The obvious question is: how reliable are our estimatesindescribingthewholepopulation?Wediscussthereliabilityofmethods ofsamplingandwaysofobtainingdata,byobservationorcontrolledexperiments. Experimental designs are discussed briefly, and in particular Latin squares are studied.Therelationofthesedesignstosudokupuzzlesismentioned. Wenextlookatgraphtheory.Thisisthestudyof(linear)graphs.Agraphconsists ofasetofobjects(calledvertices)andasetofconnectionsbetweenpairsofvertices (callededges).Forexample,theverticesmightrepresentcitiesandanedgejoining twoof themmightmeanthereisa nonstopairlineflightbetweenthose twocities; anotherexampleisthefamilytree,mentionedearlier,whereverticesarepeopleand edgesrepresentparent–childconnections. In Chap. 6 (Graphs: Traversing Roads), we start by modelling roads as edges andlookattheproblemoftraversingallroadsinanarea.Verticesmightrepresent cities,partsofatown,orintersections.TheKönigsbergbridgeproblemaskswhether onecantraverseallroadsinanareawithoutanyrepeats;eachroadistobetraveled exactlyonce.Ifthisisnotpossible,onecantrytocovereachroadatleastonce,with theminimumpossiblenumberofrepeats.Somebasicideasaboutgraphs(adjacency, multipleedges,simplicity,connectedness)arediscussed. Chapter 7 (Graphs: Visiting Vertices) starts by defining some special types of graphs,suchaspaths,cycles,andbipartitegraphs.Theproblemofvisitingalltowns inanareaexactlyonceeach—Hamilton’sproblem—andtheproblemofdoingsoas cheaplyaspossible—thetravelingsalesmanproblem—areintroduced. In Chap. 8 (More About Graphs) we discuss two further aspects of graph theory,treesandgraphcoloring.Treesaregraphsreminiscentofthetreediagrams introduced in Chap. 3. In particular, spanning trees are defined and algorithms for finding minimum cost spanning trees are outlined. Coloring and chromatic number are introduced, as are some applications of graph coloring. The famous four-colortheoremisdiscussedbriefly.Weusethischaptertoillustrateamethodof Preface ix mathematicalproof,theproofbycontradiction,whichsomereadersmaychooseto skipoveronafirstreading. Chapters 9–11 deal with numbers we actually use in everydaylife: credit card numbers, PINs, and so on. We also look at encoding and decoding, both for transmissionofdataandforsecrecy. In Chap. 9 (Identification Numbers) we look at the numbers we all use nowadays—accountnumbers, social security numbers, etc. We look at how these numbersaremadeup,andhowtheyareused.Inparticular,theformulasfordrivers’ license numbers in Illinois and Florida are explained, as well as the check digits usedincreditcards,postalmoneyorders,andbookidentificationnumbers(ISBNs) tomakesurethenumbersarelegitimateandhavebeentransmittedcorrectly. In our electronic world, much data are transmitted electronically. Computers basicallytransmitstringsofdigits,soitisnecessarytoencodeanddecodemessages. Moreover, errors can occur, so check digits are required, just as they are for identification numbers.Chapter 10 (Transmitting Data) deals with this topic. One typicalmethod,Venndiagramencoding/decoding,isexaminedindetail.Thisisan exampleofnearestneighbordecodingandisanexampleofafamilyofcodescalled Hammingcodes.Variable-lengthcodes,includingMorsecodeandthegeneticcode, are also introduced.A surprising application of Hamming codes, the hat game, is described. In Chap. 11 (Cryptography) we explore another reason for encoding material: secrecy.Thehistoryofsecretwriting,includingthe scytaleandthe Caesar cipher, isoutlined.MoremoderntechniquesincludetheVigenèremethodandsubstitution ciphers. Modular arithmetic is defined, and the RSA scheme of cryptography is studied. Thenexttwochaptersaredevotedtovoting.InChap.12(VotingSystems)some simpler voting systems and methods of deciding elections are discussed, starting with majority and plurality systems, then sequential voting and runoff elections. Preferenceprofilesaredefined.TheHaremethodforsimpleelectionsisdescribed, togetherwiththegeneralizationsoftheHaremethodcalledinstantrunoffelections. Condorcet winners are defined, along with Condorcet’s method of dealing with the case when there is no Condorcet winner. Sequential pairwise elections and pointscoremethodsareoutlined. TheninChap.13(MoreonVoting)wedescribetwomethodsforelectionswhen morethanonecandidateistobeelected:thegeneralizedHaremethodandapproval voting.Thentwomethodsofmanipulatingthevotearediscussed.Firstisstrategic voting, where voters might vote for their second favorite candidate to ensure that theirleastfavoritecandidateisnotelected(calledaninsincereballot);secondisthe introductionofamendmentstochangethefinaloutcome.Weclosewithanexample ofhowdifferentmethods,eventhoughtheyarefair,maygivedifferentresults. We finish by discussing various aspects of finance and related topics. Most readers have some idea of the mathematics of finance, but will be surprised by what they do not know. Chapter 14 (The Mathematics of Finance) covers simple and compound interest, the mathematics of compounding,and defines the annual