Project Two: Group 12.
Section 4.6: #7
Section 9.1: #32
Section 9.4: #34
Section 10.1: #12, 13
Gabrielle Krikke, Austin Brown, Pia Peredia
Background:
Eachofthesefourchaptershavedifferentkindsofmaterial.ForChapter4is
thebeginningofdifferentmethodsofproofs.Proofsneededtosolveanargument
bycontraction,contrapositive,directproofs,indirectproofs,etcetera.The
introductionofcountingisChapter9,withtheoremslikethePigeonholePrinciple
andtheBagelTheorem.Chapter10dealswithGraphTheoryandthebasicsof
graphingcircuits,paths,simplegraphs,andmuchmore.
Mathematician - Blaise Pascal
EarlyHistory:BlaisePascalwasbornin1623inFrance.Hisfather,atax
collector,wastheonewhoeducatedhimandtaughthimeverythingheoriginally
knewregardingmath.Becauseofthishehasbecomeachildprodigyandagenius
fromayoungage.Hisfatheroriginallydidnotteachhimmath.Hefocusedon
languagesandotherphilosophicalidealsinsteadofputtingimportanceonthe
sciencesandmath.
Becauseofthis,Pascalwassoeagertolearnmath.Hequicklybeganlearning
allaboutthemathworld.Hisfirstlargecontributiontothescientificcommunitywas
anearlydesign/modelforacalculator.Hecreatedittohelphisfathercounttax
information.Thiswasarevolutionaryidea,andhecameupwithitallonhisownat
theageofeighteen.
Afterhecreatedthecalculator,Pascaldecidedtobranchout.Hespentalot
oftimeponderinglifeandotherphilosophicalissues.Healsospentsometime
studyingtheEarthandhowitworks.Helearnedalotabouttheatmosphereandthe
pressuresthatcreatethelayersthatallowustolivehereonEarth.Becausehe
discoveredsomuchaboutthemakeupoftheatmosphere,hehasaunitof
measurementnamedafterhim.
Hethenreturnedtothemathworldandhelpedcreatesomeoftheearliest
ideasregardingprobability.Thisisthemostimportantpartofhislifeforthisclass.
WithoutPascal,thepigeonholetheorywouldnotexistorbeasthoroughlythought
outasitistoday.HeworkedalongwithPierredeFermat,anothermathematician,
andobservedprobabilityforthefirsttime.Theyrealizedthatthingsdidnotjust
happenatrandom,andthattherewasasetlikelihoodofeventstooccur.Their
experimentswerealldonewithdice,buttheyquicklyrealizedthattheirdiscoveries
couldbetransferredtoanysituationthatinvolvedchance.
Pascaldiedin1662athissistershouse.Hehadseveralhealthproblemsand
workingasmuchashediddefinitelydidnothelphisbodyheal.Heendedupdying
becauseoftumorthatstartedinhisstomachandthenmovedtohisbrain.Pascal
onlylivedtobe39,butinthatshortamountoftimehecreatedandrevolutionized
manypiecesofmodernmathematicsandscience.
Problems:
Section4.6:#7
1.Statetheproblem:
Thereisnoleastpositiverationalnumber.
2.Setuptheproofbycontradiction:
Supposetheabovestatementisfalse.
Then,thereexistsaleastpositiverationalnumber,calledR.
ThismeansthatRrforallrationalnumbersr.
LetR=a/b,forintegersa,b,b0.
Multiplybby2togetR=a/2b.
Risstillapositiverationalnumber.
R<R,becausetheyhavethesamenumerator,andRhasalarger
denominator.
ThismeansthatRissmallerthantheleastpositiverationalnumber.
3.Statetheconclusion:
Therefore,itisacontradiction.Theoriginalstatementistrue.
Section9.1:#32Part(a)
1.Statetheproblem:
Acertainnonleapyearhas365days,andJanuaryoccursonaMonday.
a.)HowmanySundaysareintheyear?
2.Createavisualizationtoestablishapattern:
M Tu W Th F Sa Su M Tu W Th F Sa Su
1 2 3 4 5 6 7 8 9 10 11 12 13 14
ThefirstSundayoftheyearisonJanuary7th.ThenextSundayisonJanuary
14th.Therefore,thepatternisthatSundasfallonmultiplesofseven.
TodeterminehowmanySundaysareinayear,identifythehighestmultiple
ofseventhatisequaltoorlessthan365(daysinanonleapyear).
3647=52
3.Statetheconclusion:
Therefore,thereare52Sundaysintheyear.
Section9.1:#32Part(b)
1.Statetheproblem:
Acertainnonleapyearhas365days,andJanuaryoccursonaMonday.
b.)HowmanyMondaysareintheyear?
2.Createavisualizationtoestablishapattern:
M Tu W Th F Sa Su M Tu W Th F Sa Su
1 2 3 4 5 6 7 8 9 10 11 12 13 14
UsetheinformationcalculatedfrompartAtofinishthelasttwodaysofthe
year.
Su M
364 365
IfthelastSundayoftheyearwasthe52ndSunday,thenthelastMondayof
theyearwouldbethe53rdMonday.
3.Statetheconclusion:
Therefore,thereare53Mondaysintheyear.
Section9.4:#34:
1.Statethequestion:
LetSbeasetoftenintegerschosenfrom1through50.Showthattheset
containsatleasttwodifferent(butnotnecessarilydisjoint)subsetsoffourintegers
thatadduptothesamenumber.
2.Solution
Firstyoumustfindthepossiblenumberofsubsetsfromtheoriginalten
numbers.Use
10
C
4
10!/(104)!*4!=10*9*8*7/4*3*2*1=210possiblesubsets.
Nowwemustdecidehowmanypossiblesumsthereare.Inordertodothis
wetakethehighestpossiblesumandsubtractthelowestsum.Thiswillgiveusthe
rangeofsumsthatarepossiblebetween1and50.
(50+49+48+47)(1+2+3+4)=(194)(10)=184
Andnowbasedonthepigeonholetheory,weknowthatthereareatleast
twosubsetsthatexistwithintheoriginalsetthatadduptothesamenumber.
3.Conclusion
210(possiblesubsets)>184(totalsumspossible)
Becausetheyarenotequal,thepigeonholetheoryapplies.Andatleasttwo
pigeons(subsets)havetoflyintothesamehole(sum).
Section10.1:#12:
1.Statethequestion:
Fromaninitialpositionontheleftbankofariver,theferrymanisto
transportawolf,agoat,andabagofcabbagetotherightbank.Unfortunately,the
ferrymansboatcanonlytransportoneobjectatatime,otherthanhimself.
Nonetheless,forobviousreasons,thewolfcannotbeleftalonewiththegoat,and
thegoatcannotbeleftalonewiththecabbage.Howcantheferrymanproceed?
2.Process:(twopossiblesolutions)
Letwolf=w,goat=g,cabbage=c,andtheferryman=f
Solution1:
LeftBank: RightBank:
Start: 1) wgcf 0
2) wgcf gf 0
3) wc gf
4) wc f gf
5) wcf g
6) c wf g
7) c wgf
8) c gf wc
9) gcf w
10) g cf w
11) g wcf
12) g f wc
13) gf wc
14) 0 gf wc
End: 15) 0 wgcf
Solution2:(Itsthesameprocess,howeverthewolfandthecabbage
switchsteps.)
LeftBank: RightBank:
Start: 1) wgcf 0
2) wgcf gf 0
3) wc gf
4) wc f gf
5) wcf g
6) w cf g
7) w gcf
8) w gf c
9) wgf c
10) g wf c
11) g wcf
12) g f wc
13) gf wc
14) 0 gf wc
End: 15) 0 wgcf
3.Conclusion:
Aspreviouslystated,thedifferencesbetweenthetwosolutionsis
whichispickedfirst:thewolforthecabbageasshowninboth
solutionsatStep6(whichishighlighted).Eitherwayworksaslongas
thewolfisnotalonewiththegoatandthegoatisnotalonewiththe
cabbage.
Section10.1:#13:
1.Statetheproblem:
Onanislandtherearetwokindsofpeople:vegetariansandcannibals.
Therearethreevegetariansandthreecannibalsontheleftbankofariver.Withthem
thereisaboatthatcanholdamaximumoftwopeople,yetthecannibalscannot
outnumberthevegetariansatanytimeoneitherbank.Howcantheyallgetonthe
rightbankoftheriver?
2.Process:
Letthevegetarians=vandthecannibals=c
LeftBank: RightBank:
Start: 1) cccvvv 0
2) ccvv cv 0
3) ccvv cv
4) ccvv v c
5) ccvvv c
6) vvv cc c
7) vvv ccc
8) vvv c cc
9) cvvv cc
10) cv vv cc
11) cv ccvv
12) cv cv cv
13) ccvv cv
14) cc vv cv
15) cc cvvv
16) cc c cvvv
17) ccc vvv
18) c cc vvv
19) c ccvvv
20) c c cvvv
21) cc cvvv
22) 0 cc cvvv
End: 23) 0 cccvvv
3.Conclusion:
Comparedtotheferrymanproblem,thisproblemhastheexact
processbutinsteadof15stepsthereare23.Asyoucansee,themore
variablesorobjects,themorestepsitwilltaketogettotheendsolution.Ifit
wastobedrawnout,thischartitwilltakeashapeofagraph.
Summary:
Insummary,theseproblemscoveredmanyaspectsofDiscreteMathematics.
ThePigeonHoletheoremiscoveredinchapter9section4.Itisbasicallythe
ideathatcertainscenariosareguaranteedtooccurifthefunctionthatthescenario
takesplaceinisnotaonetoonefunction.Aslongastherearemorepigeons
thanpigeonholesthereisacertainprobabilitythatadesiredscenariowilloccur.
Theseideascouldnothavebeenpossiblewithoutthemathematicianwe
chosetoobserve.BlaisePascal,aFrenchmathematician,scientist,and
philosopher,studiedandperfectedmanythingsthroughouthisshortlifetime.He
createdacalculator,maderevolutionaryobservationsabouttheatmosphere,and
evenpavedthewayforSirIsaacNewton.But,withthissectioninmind,his
greatestaccomplishmentwasthefirstunderstandingofprobability.Hediscovered
thateverythinginlifeisnotrandom,andthattheprobabilityofeventscanactually
befiguredout.HealsohelpedcreatethePigeonHoletheorem.
Now,agraphconsistsoftwofinitesets:anonemptysetofverticesanda
setofedges,whereeachedgeisassociatedwithasetconsistingofeitheroneor
twoverticescalledendpoints.Thecorrespondencefromedgestoendpointsis
calledtheedgeendpointfunction.Graphsareapowerfulproblemsolvingbecause
theyenableustorepresentacomplexsituationwithasingleimagethatcanbe
analyzed.
References:
Epp,SusannaS.DiscreteMathematicswithApplications.Belmont,CA:
ThomsonBrooks/Cole,2004.Print.
"BlaisePascal."Bio.A&ETelevisionNetworks,2014.Web.14May2014.
"BlaisePascal."Wikipedia.WikimediaFoundation,05Nov.2014.Web.14May2014.
