MATH2069_DiscreteMathematicsAndGraphTheory_2014 Semester 1_tute02

University of Sydney_MATH2069_DiscreteMathematicsAndGraphTheory_2014 Semester 1

TheUniversityofSydney

SchoolofMathematicsandStatistics

Tutorial2(Week3)

Moredi cultquestionsaremarkedwitheither*or**.Thosemarked*areatthelevelwhichMATH2069studentswillhavetosolveinordertobesureofgettingaCredit,ortohaveachanceofaDistinctionorHighDistinction.Thosemarked**aremainlyintendedforMATH2969students.Somenumericalanswersareattheendofthesheet.

1.Supposeyouhave7di erentornamentstoputonyourmantelpiece.

(a)Ifyouwanttouseallofthem,howmanypossiblearrangementsarethere?(b)Ifyouwanttouse6ofthem,howmanypossiblearrangementsarethere?(c)Ifyoucanuseall,some,ornoneofthem,howmanypossiblearrangements

arethere?

*(d)Divideyouranswertopart(c)byyouranswertopart(a);thisratiomeasures

howmuchextrafreedomyougetbynotnecessarilyusingalltheornaments.

Noticethatitagreeswitheuptofourdecimalplaces.Isthisacoincidence?

2.Anordinaryknock-outsinglestennistournament(withnoseedsorbyes)consists

ofaseriesofrounds.Ineachround,theremainingplayersplayagainsteachotherinpairs,withthelosersbeingeliminatedandthewinnersgoingthroughtothenextround;inthelastround,theonlytworemainingplayersplaythe nalmatchtodeterminethewinnerofthetournament.Supposethatthereare7rounds.

(a)Howmanyplayersarethereatthestartofthetournament?

(b)Howmanymatchesareplayedintotal?

(c)Beforethetournamentstarts,theorganizersneedtoconstructthedraw,

whichspeci eswhoplayswhointhe rstround,andthenwhich rst-round

winnersplaywhichother rst-roundwinnersinthesecondround,andsoon.

Ofcourse,theorganizersdon’tknowwhothe rst-roundwinnerswillbe,so

inthedrawtheyarejustthoughtofas“thewinnerofthematchbetween

playerXandplayerY”,andsoforth.Howmanypossibledrawsarethere?

Usethefact,provedinlectures,thatthenumberofwaystogroup2kpeople(2k)!intokpairsis

第1页下一页