3離散數(shù)學(xué)及其應(yīng)用英文版第6版課后答案(美KennenthH.Rosen著)機(jī)械工業(yè)出版社

1、P.161.14.IfIdidnotbuyalotteryticketthisweek,thenIdidnotwinthemilliondollarjackpotonFriday.Ididnotbuyalotteryticketthisweek,andIdidnotwinthemilliondollarjackpotonFriday.h)EitherIdidnotbuyalotteryticketthisweek,orelseIdidbuyoneandwonthemilliondollarjackpotonFriday.10.a)rAqqb)pAqArc)rfpd)pAqqAre)(pAq)f

2、rf)r(qVp)20.IfIamtoremembertosendyoutheaddress,thenyouwillhavetosendmeane-mailmessage.(Thishasbeenslightlyrewordedsothatthetensesmakemoresense.)IfyouwerebornintheUnitedStates,thenyouareacitizenofthiscountry.Ifyoukeepyourtextbook,thenitwillbeausefulreferenceinyourfuturecourses.(Thewordthenisunderstoo

3、dinEnglish,evenifomitted.)Iftheirgoaltenderplayswell,thentheRedWingswillwintheStanleyCup.Ifyougetthejob,thenyouhadthebestcredentials.Ifthereisastorm,thenthebeacherodes.Ifyoulogontotheserver,thenyouhaveavalidpassword.Ifyoudontbeginyourclimbtoolate,thenyouwillreachthesummit.33.c)pqr(pfq)“pfr)TTTTTTFTT

4、FTTTFFTFTTTFTFTFFTTFFFTP.261.28.Kwamewillnottakeajobinindustryandhewillnotgotograduateschool.YoshikodoesntknowJavaorshedoesntknowcalculus.Jamesisnotyoungorheisnotstrong.RitawillnotmovetoOregonandshewillnotmovetoWashington.10.a)PqIPpVqqpA(pVq)hpA(pVq)fqTTFTFTTFFTFTFTTTTTFFTFFTc)PqpfqPA(pfq)PA(pfq)fqT

5、TTTTTFFFTFTTFTFFTFT12.Assumethehypothesisistrue.Thenpisfalse.SincepVqistrue,weconcludethatqmustbetrue.Hereisamorealgebraicsolution:hpA(pVq)fqihpA(PVq)VqiipV|(pVq)VqpVq(pVq)Vq(pVq)Vq(pVq)TAssumethehypothesisistrue.Thenpistrue,andsincethesecondpartofthehypothesisisture,weconcludethatqisalsotrue,asdesi

6、red.24.pqrpqpr(pq)V(pr)qVrp(qVr)TTTTTTTTTTFTFTTTTFTFTTTTTFFFFFFFFTTTTTTTFTFTTTTTFFTTTTTTFFFTTTFT30.pqrpVqqpVrqVr(pVq)A(qpVr)(pVq)A(qpVr)(qVr)TTTTTTTTTTFTFTFTTFTTTTTTTFFTFFFTFTTTTTTTFTFTTTTTFFTFTTFTFFFFTFFT51.(pJp)Jq兒(pJp)Jq)9.77.Thegraphisplanar.20.ThegraphisnothomeomorphictoK3,3,sincebyreroutingthe

7、edgebetweenaandhweseethatitisplanar.Replaceeachvertexofdegreetwoanditsincidentedgesbyasingleedge.ThentheresultisK3,3:thepartsarea,e,iandc,g,k.ThereforethisgraphishomeomorphictoK3,3.Thegraphisplanar.25.Thegraphisnotplanar.9.210.417.timeslot1:Math115,Math185;timeslot3:Math195,CS101;timeslot5:

8、CS273timeslot2:Math116,CS473;timeslot4:CS102P.461.33.a)trueb)falsec)falsed)falsea)Thereisastudentwhospendsmorethan5hourseveryweekdayinclass.Everystudentspendsmorethan5hourseveryweekdayinclass.Thereisastudentwhodoesnotspendmorethan5hourseveryweekdayinclass.Nostudentspendsmorethan5hourseveryweekdayinc

9、lass.9.a)-x(P(x)AQ(x)b)X(P(x)AQ(x)x(P(x)vQ(x)d)Vx(P(x)vQ(x)16.a)trueb)falsec)trued)falseLetC(x)bethepropositionalfunction“xisinyourclass.”VxP(x)andx(C(x)fP(x),whereP(x)is“xhasacellularphone.”日xF(x)and日x(C(x)AF(x),whereF(x)is“xhasseenaforeignmovie.”曰xS(x)and日x(C(x)AS(x),whereS(x)is“xcanswim.”VxE(x)an

10、dVx(C(x)fE(x),whereE(x)is“xcansolvequadraticequations.”-弓xR(x)and弓x(C(x)AR(x),whereR(x)is“xwantstoberich.”62.Vx(P(x)fS(x)b)燈x(R(x)fS(x)vx(Q(x)fP(x)d)燈x(Q(x)fR(x)Yes.Ifxisoneofmypoultry,thenheisaduck(bypart(c),hencenotwillingtowaltz(part(a).Sinceofficersarealwayswillingtowaltz(part(b),xisnotanofficer

11、.P.591.412.VxqC(x,Bob)xVy(I(x)A(x豐y)-qI(y)k)dxVy(I(x)AqC(x,y)n)-5x3yVz(x豐y)Aq(C(x,z)AC(y,z)14.-xH(x),whereH(x)is“xcanspeakHindi”andtheuniverseofthediscourseconsistsofallstudentsinthisclass.Vx日yP(x,y),whereP(x,y)is“xplaysy.”andtheuniverseofthediscourseforxconsistsofallstudentsinthisclass,andtheuniver

12、seofthediscourseforyconsistsofallsports.弓xA(x)AqH(x),whereA(x)is“xhasvisitedAlaska.”,H(x)is“xhasvisitedHawaii”andtheuniverseofthediscourseforxconsistsofallstudentsinthisclass.燈x-yL(x,y),whereL(x,y)is“xhaslearnedprogramminglanguagey”andtheuniverseofthediscourseforxconsistsofallstudentsinthisclass,and

13、theuniverseofthediscourseforyconsistsofallprogramminglanguages.dxdzvy(Q(y,z)P(x,y),whereP(x,y)is“xhastakencoursey.”，Q(y,z)is“courseyisofferedbydepartmentz.”,andtheuniverseofthediscourseforxconsistsofallstudentsinthisclass,theuniverseofthediscourseforyconsistsofallcoursesinthisschool,andtheuniverseof

14、thediscourseforzconsistsofalldepartmentsinthisschool.xy燈z(x主y)AP(x,y)A(x主y主z)qP(x,z),whereP(x,y)is“xandygrewupinthesametown.”andtheuniverseofthediscourseforx,y,zconsistsofallstudentsinthisclass.Vx日y日zC(x,y)AG(y,z),whereC(x,y)is“xhaschattedwithy”,G(y,z)is“yisinchatgroupz”,theuniverseofthediscoursefor

15、x,yconsistsofallstudentsinthisclass,andtheuniverseofthediscourseforzconsistsofallchatgroupinthisclass.9.rSimplificationusingStep824.Thereisanadditiveidentityfortherealnumbers.Theproductoftwononzeronumbersisnonzerofortherealnumbers.38.Therearenostudentsinthisclasswhohaveneverseenacomputer.Therearenos

16、tudentsinthisclasswhohavetakenbeeninatleastoneroomofeverybuildingoncampus.(|rA(qfp)f(pf(qVr)n(qrA(qqVp)V(qpV(qVr)(qAqp)V(qpVqVr)(qpVqVrVq)A(qpVqVrVqp)(qpVqVr)丫0,1,2,4,5,6,7P.72LetrbethepropositionItrains,letfbethepropositionItisfoggy,letsbethepropositionThesailingracewillbeheld,letlbethepropositionT

17、helifesavingdemonstrationwillgoon,andlettbethepropositionThetrophywillbeawarded.Wearegivenpremises仃rVqf)(sAl),sft,andqt.Wewanttoconcluder.Wesetuptheproofintwocolumns,withreasons.Notethatitisvalidtoreplacesubexpressionsbyotherexpressionslogicallyequivalenttothem.StepReasonqtHypothesissftHypothesisqsM

18、odustollensusingSteps1and2(qrVqf)f(sAl)Hypothesis(q(sAl)fq(qrVqf)Contrapositiveofstep4(qsVql)f(rAf)DeMorganslawanddoublenegativeqsVqlAddition,usingStep3rAfModusponensusingStep6and7Stepqqf(uAt)uAt HYPERLINK l bookmark2uufp HYPERLINK l bookmark94ptpAt(pAt)f(rVs) HYPERLINK l bookmark4rVsqs HYPERLINK l

19、bookmark16r12.First,usingtheconclusionofExercise11,weshouldshowthattheargumentformwithpremises(pAt)f(rVs),qf(uAt),ufp,qs,q,andconclusionrisvalid.Then,weuserulesofinferencefromTable1.ReasonPremisePremiseModusponensusingSteps1and2SimplificationusingStep3PremiseModusponensusingSteps3and4Simplificationu

20、singStep3ConjunctionusingSteps6and7PremiseModusponensusingSteps8and9PremiseDisjunctivesyllogismusingSteps10and1114LetR(x)be“xisoneofthefiveroommates,”D(x)be“xhastakenacourseindiscretemathematics,”andA(x)be“xcantakeacourseinalgorithms.”Thepremisesare燈x(R(x)fD(x),vx(D(x)fA(x)andR(Melissa).Usingthefirs

21、tpremiseandUniversalInstantiation,R(Melissa)fD(Melissa)follows.UsingthethirdpremiseandModusPonens,D(Melissa)follows.UsingthesecondpremiseandUniversalInstantiation,A(Melissa)follows.Sodotheotherroommates.d)LetC(x)be“xisintheclass,”F(x)be“xhasbeentoFrance,”andL(x)be“xhasvisitedLouvre.”Thepremisesare日x

22、(C(x)AF(x)andx(F(x)fL(x).FromthefirstpremiseandExistentialInstantiationimplythatC(y)AF(y)foraparticularpersony.UsingSimplification,F(y)follows.UsingthesecondpremiseandUniversalInstantiationF(y)fL(y)follows.UsingModusPonens,L(y)follows.UsingExistentialGeneralization,弓x(C(x)AL(x)follows.24.Theerrorsoc

23、curinsteps(3),(5)and(7).Forsteps(3)and(5),wecannotassume,asisbeingdonehere,thatthecthatmakesP(x)trueisthesameasthecthatmakesQ(x)trueatthesametime.Forstep(7),itisnotaconjunctionandthereisnosuchdisjunctionrule.29.StepReason1.-xqP(x)2.qP(c)Vx(P(x)VQ(x)P(c)VQ(c)PremiseExistentialinstantiationfrom(1)Prem

24、iseUniversalinstantiationfrom(3)5.Q(c)Disjunctivesyllogismfrom(2)and(4)6.Vx(qQ(x)VS(x)Premise7.qQ(c)VS(c)Universalinstantiationfrom(6)8.S(c)Disjunctivesyllogismfrom(5)and(7)9.vx(R(x)fqS(x)Premise10.R(c)fqS(c)Universalinstantiationfrom(9)11.qR(c)Modustollensfrom(8)and(10)12.-xqR(x)Existentialgenerali

25、zationfrom(11)P.861.6SupposethatPlfP4fP2fP5fP3fPl.Toprovethatoneofthesepropositionsimpliesanyoftheothers,justusehypotheticalsyllogismrepeatedly.P.1031.713.Thisstatementassertstheexistenceofxwithacertainproperty.Ifwelety=x,thenweseethatP(x)istrue.Ifyisanythingotherthanx,thenP(x)isnottrue.Thus,xistheu

26、niqueelementthatmakesPtrue.ThefirstclauseheresaysthatthereisanelementthatmakesPtrue.ThesecondclausesaysthatwhenevertwoelementsbothmakePtrue,theyareinfactthesameelement.TogetherthesesaythatPissatisfiedbyexactlyoneelement.ThisstatementassertstheexistenceofanxthatmakesPtrueandhasthefurtherpropertythatw

27、heneverwefindanelementthatmakesPtrue,thatelementisx.Inotherwords,xistheuniqueelementthatmakesPtrue.P.1202.1TTFTTF16.Sincetheemptysetisasubsetofeveryset,wejustneedtotakeasetBthatcontainsasanelement.ThuswecanletA=andB=asthesimplestexample.20.TheunionofthesetsinthepowersetofasetXmustbeexactlyX.Inotherw

28、ords,wecanrecoverXfromitspowerset,uniquely.Thereforetheanswerisyes.22.Thepowersetofeverysetincludesatleasttheemptyset,sothepowersetcannotbeempty.Thusisnotthepowersetofanyset.ThisisthepowersetofaThissethasthreeelements.Since3isnotapowerof2,thissetcannotbethepowersetofanyset.Thisisthepowersetofa,b.28.

29、(a,x,0),(a,x,1),(a,y,0),(a,y,1),(b,x,0),(b,x,1),(b,y,0),(b,y,1),(c,x,0),(c,x,1),(c,y,0),(c,y,1)(0,a,x),(0,a,y),(0,b,x),(0,b,y),(0,c,x),(0,c,y),(1,a,x),(1,a,y),(1,b,x),(1,b,y),(1,c,x),(1,c,y)P.1302.214.SinceA=(A-B)U(APB),weconcludethatA=1,5,7,8U3,6,9=1,3,5,6,7,8,9.SimilarlyB=(B-A)U(APB)=2,10U3,6,9=2,

30、3,6,9,10.24.Firstsupposexisintheleft-handside.ThenxmustbeinAbutinneitherBnorC.ThusxWA-C,butx氓B-C,soxisintheright-handside.Nextsupposethatxisintheright-handside.ThusxmustbeinA-CandnotinB-C.ThefirstoftheseimpliesthatxWAandx氓C.Butnowitmustalsobethecasethatx芒B,sinceotherwisewewouldhavexWB-C.Thuswehavesh

31、ownthatxisinAbutinneitherBnorC,whichimpliesthatxisintheleft-handside.40.Thisisanidentity;eachsideconsistsofthosethingsthatareinanoddnumberofthesetsA,B,andC.P147.2.335Thisreallyhastwoparts.Firstsupposethatbisinf(SUT).Thusb=f(a)forsomeaWSUT.EitheraWS,inwhichcasebWf(S),oraWT,inwhichcasebWf(T).Thusineit

32、hercasebWf(S)Uf(T).Thisshowsthatf(SUT)f(S)Uf(T),Conversely,supposebWf(S)Uf(T).TheneitherbWf(S)orbWf(T).Thismeanseitherthatb=f(a)forsomeaWSorthatb=f(a)forsomeaWT.Ineithercase,b=f(a)forsomeaWSUT,sobWf(SUT).Thisshowsthatf(S)Uf(T)f(SUT),andourproofiscomplete.SupposebWf(SPT).Thenb=f(a)forsomeaWSPT.Thisim

33、pliesthataWSandaWT,sowehavebWf(S)andbWf(T).ThereforebWf(S)Pf(T),asdesired.52Insomesensethisquestionisitsownanswerthenumberofintegersbetweenaandb,inclusive,isthenumberofintegersbetweenaandb,inclusive.Presumablyweseekanexpressinvolvinga,b,andthefloorand/orceilingfunctiontoanswerthisquestion.Ifwerounda

34、upandroundbdowntointegers,thenwewillbelookingatthesmallestandlargestintegersjustinsidetherangeoftheintegerswewanttocount,respectively.Thesevaluesareofcourseaand_b，respectively.Thentheansweris_ba+1(justthinkofcountingalltheintegersbetweenthesetwovalues,includingbothendsifarowoffencepostsonefootaparte

35、xtendsforkfeet，thentherearek+1fenceposts).Notethatthisevenworkswhen,forexample,a=0.3andb=0.7.P1622.434.Thisiscountable.Theintegersinthesetare1,2,4,5,7,andsoon.Wecanlistthesenumbersintheorder1,-1,2,-2,4,-4,.,therebyestablishingthedesiredcorrespondence.Inotherwords,thecorrespondenceisgivenby11,2-1,32,

36、4-2,54,andsoon.Thisissimilartopart(a);wecansimplylisttheelementsofthesetinorderofincreasingabsolutevalue,listingeachpositivetermbeforeitscorrespondingnegative:5,-5,10,-10,15,-15,20,-20,30,-30,40,-40,45,-45,50,-50,.Thisiscountablebutalittletricky.Wecanarrangethenumbersina2-dimensionaltableasfollows:.

37、110.11110.11111.1111.111111.11111.111.1111.11111.1111111.1111111.1111.11111.111111.1111Thissetisnotcountable.WecanproveitbythesamediagonalizationargumentaswasusedtoprovethatthesetofallrealsisuncountableinExample21.Allweneedtodoischoosed=1whend=9andchoosed=9whend=1ordisblank(ifi

38、iiiiiiithedecimalexpansionisfinite)46.WeknowfromExample21thatthesetofrealnumbersbetween0and1isuncountable.Letusassociatetoeachrealnumberinthisrange(including0butexcluding1)afunctionfromthesetofpositiveintegerstotheset0,1,2,3,4,5,6,7,8,9asfollows:Ifxisarealnumberwhosedecimalrepresentationis0.d1d2d3(w

39、ithambiguityresolvedbyforbiddingthedecimaltoendwithaninfinitestringof9s),thenweassociatetoxthefunctionwhoseruleisgivenbyf(n)=dn.clearlythisisaone-to-onefunctionfromthesetofrealnumbersbetween0and1andasubsetofthesetofallfunctionsfromthesetofpositiveintegerstheset0,1,2,3,4,5,6,7,8,9.Twodifferentrealnum

40、bersmusthavedifferentdecimalrepresentations,sothecorrespondingfunctionsaredifferent.(Afewfunctionsareleftout,becauseofforbiddingrepresentationssuchas0.239999.)Sincethesetofrealnumbersbetween0and1isuncountable,thesubsetoffunctionswehaveassociatedwiththemmustbeuncountable.Butthesetofallsuchfunctionsha

41、satleastthiscardinality,soit,too,mustbeuncountable.P1913.21.ThechoicesofCandkarenotunique.a)YesC=1,k=10b)YesC=4,k=7c)NoYesC=5,k=1e)YesC=1,k=0f)YesC=1,k=29.x2+4x+1717,sox2+4x+17isO(x3),withwitnessesC=3,k=17.However,訐x3wereO(x2+4x+17),thenx3C(x2+4x+17)3Cx2forsomeC,forallsufficientlylargex,whichimplies

42、thatx3C,forallsufficientlylargex,whichisimpossible.P2093.419.a)nob)noc)yesd)no31.a)GRQRWSDVVJRb)QBABGCNFFTBc)QXUXMAHJJZXP2183.513.a)Yesb)Noc)Yesd)Yes17a)2b)4c)12P2804.122.Alittlecomputationconvincesusthattheansweristhatn24.(clearlytheinequalitydoesntholdforn=2orn=3)Wewillprovebymathematicalinduction

43、thattheinequalityholdsforalln4.Thebasecaseisclear,since1624.Nowsupposethatn24.Wemustshowthat(n+1)2(n+1)!.Expandingtheleft-handside,applyingtheinductivehypothesis,andtheninvokingsomevalidboundsshowsthis:n2+2n+1n!+2n+1n!+2n+1=n!+3nn!+nnn!+nn!59.1.BecauseP(1)AP(2)AAP(m-1)P(m)istrue,itfollowsthatP(m)mus

44、talsobetrue,whichisacontradiction.Hence,S=0.P3084.310.ThebasecaseisthatSm(0)=m.TherecursivepartisthatSm(n+1)isthesuccessorofS(n)(i.e.,S(n)+1)mm12.Thebasecasen=1isclear,sincef12=f1f2=1.Assumetheinductivehypothesis.Thenf12+f22+.+fn2+fn+12=fn+12+fnfn+1=fn+1(fn+1+fn)=fn+1fn+2,asdesired.12nn+1n+1nn+1n+1n

45、+1nn+1n+231.Ifxisasetorvariablerepresentingset,thenxiswell-formedformula.ifxandyareallwell-formedformulas,thenx,(xUy),(xAy)and(x-y)areallwell-formedformulas.50.LetP(n)be“A(1,n)=2n.”BASICSTEP:P(1)istrue,becauseP(1)=A(1,1)=2=21.INDCUTIVESTEP:AssumethatP(m)istrue,thatisA(1,m)=2mandm1.ThenP(m+1)=A(1,m+1

46、)=A(0,A(1,m)=A(0,2m)=22m=2m+1.SoA(1,n)=2nwhenevern1Notwelldefined.F(2)isnotdefinedsinceF(0)isnt.Also,F(2)isambiguous.Notwelldefined.Thedefinitionisambiguousaboutn=1.P3445.13.a)410b)51012.Weusethesumrule,addingthenumberofbitstringsofeachlengthupto6.Ifweincludetheemptystring,thenweget02+21+22+23+24+25

47、+26=27-1=12720.Everyseventhnumberisdivisibleby7.Thereforethereare999/7=142suchnumbers.Notethatweusethefloorfunction,becausethekthmultipleof7doesnotoccuruntilthenumber7khasbeenreached.Forsolvingthispartandthenextfourparts,weneedtousetheprincipleofinclusion-exclusion.Justasinpart(a),thereare999/11=90n

48、umbersinourrangedivisibleby11,andthereare999/77=12numbersinourrangedivisiblebyboth7and11(themultiplesof77arethenumbersweseek).Ifwetakethese12numbersareawayfromthe142numbersdivisibleby7,weseethatthereare130numbersinourrangedivisibleby7butnotby11.asexplainedinpart(b),theansweris12.Bytheprincipleofincl

49、usion-exclusion,theanswer,usingthedatafrompart(b),is142+90-12=220.Ifwesubtractfromtheanswertopart(d)thenumberofnumbersdivisiblebyneitherofthem;sotheansweris220-12=208.Ifwesubtracttheanswertopart(d)fromthetotalnumberofpositiveintegerslessthan1000,wewillhavethenumberofnumbersdivisiblebyexactlyoneofthe

50、m;sotheansweris999-220=779.Ifweassumethatnumbersarewrittenwithoutleading0s,thenweshouldbreaktheproblemdownintothreecases-one-digitnumbers,two-digitnumbers.Clearlythereare9one-digitnumbers,andeachofthemhasdistinctdigits.Thereare90two-digitnumbers(10through99),andallbut9ofthemhavedistinctdigits.Analte

51、rnativewaytocomputethisistonotethatthefirstdigitmustbe1through9(9choices)andtheseconddigitmustbesomethingdifferentfromthefirstdigit(9choicesoutofthe10possibledigits),sobytheproductrule,weget9*9=81choicesinall.Thisapproachalsotellsusthatthereare9*9*8=648three-digitnumberswithdistinctdigits(again,work

52、fromlefttoright-intheonesplace,one8digitsarelefttochoosefrom).80thefinalansweris9+81+648=738.Itturnsouttobeeasiertocounttheoddnumberswithdistinctdigitsandsubtractfromouranswertopart(g),soletusproceedthatway.Thereare5oddone-digitnumbers.Fortwo-digitnumbers,firstchoosetheonedigit(5choices),thenchooset

53、hetensdigits(8choices),sinceneithertheonesdigitvaluenot0isavailable);thereforethereare40suchtwo-digitnumbers.(Notethatthisisnotexactlyhalfof81.)Forthethree-digitnumbers,firstchoosetheonesdigit(5choices),thenthehundredsdigit(8choices),thenthetensdigit(8choices),givingus320inall.Sothereare5+40+320=365

54、oddnumberswithdistinctdigits.Thusthefinalansweris738-365=373.35.a)若n=1,為2；若n=2,為2;若n=3,為0對(duì)于nl,為2n_2；若n=1,為1；2(n-1)(注：n可映射到0,1兩種可能)44.Firstwecountthenumberofbitstringsoflength10thatcontainfiveconsecutive0s.Wewillbasethecountonwherethestringoffiveormoreconsecutive0sstarts.Ifitstartsinthefirstbit,thent

55、hefirstfivebitsareall0s,butthereisfreechoiceforthelastfivebits;thereforethereare25=32suchstrings.Ifitstartsinthesecondbit,thenthefirstbitmustbea1,thenextfivebitsareall0s,butthereisfreechoiceforthelastfourbits;thereforethereare24=16suchstrings.Ifitstartsinthethirdbit,thenthesecondbitmustbea1butthefir

56、stbitandthelastthreebitsarearbitrary;thereforethereare24=16suchstrings.Similarly,thereare16suchstringsthathavetheconsecutive0sstartingineachofpositionsfour,five,andsix.Thisgivesusatotalof32+5X16=112stringsthatcontainfiveconsecutive0s.Symmetrically,thereare112stringsthatcontainfiveconsecutive1s.Clear

57、lythereareexactlytwostringsthatcontainboth(0000011111,1111100000).Thereforebytheinclusion-exclusionprinciple,theansweris2*(112)-2=222.30.a)C(16,5)-C(9,5)=4242b)C(16,5)-C(9,5)-C(7,5)=422138.52.Wedrawthetree,withitsrootatthetop.Weshowabranchforeachofthepossibilities0and1,foreachbitinorder,exceptthatwe

58、donotallowthreeconsecutive0s.Sincethereare13leaves,theansweris13.secondbitthirdbitfourthbitP3535.26.Thereareonlydpossibleremainderswhenanintegerisdividedbyd,namely0,1,d-1.Bythepigeonholeprinciple,ifwehaved+1remainders,thenatleasttwomustbethesame.10.Themidpointofthesegmentwhoseendpointsare(a,b)and(c,

59、d)is(a+c)/2,(b+d)/2).Weareconcernedonlywithintegervaluesoftheoriginalcoordinates.Clearlythecoordinatesofthesefractionswillbeintegersaswellifandonlyifaandchavethesameparity(bothoddorbotheven)andbanddhavethesameparity.Thuswhatmattersinthisproblemistheparitiesofcoordinates.Therearefourpossiblepairsofpa

60、rities:(odd,odd),(odd,even),(even,even)and(even,odd).Sincewearegivenfivepoints,thepigeonholeprincipleguaranteesthatatleasttwoofthemwillhavethesamepairofparties.Themidpointofthesegmentjoiningthesetwopointswillthereforehaveintegercoordinates.Tb)TT1aaa125,and26a+25a+25.a+25150.12751275Noweitherofthese1