3离散数学及其应用 英文版 第6版 课后答案(美 kennenth h.rosen 著) 机械工业出版社

P16114FIFIDIDNOTBUYALOTTERYTICKETTHISWEEK,THENIDIDNOTWINTHEMILLIONDOLLARJACKPOTONFRIDAYGIDIDNOTBUYALOTTERYTICKETTHISWEEK,ANDIDIDNOTWINTHEMILLIONDOLLARJACKPOTONFRIDAYHEITHERIDIDNOTBUYALOTTERYTICKETTHISWEEK,ORELSEIDIDBUYONEANDWONTHEMILLIONDOLLARJACKPOTONFRIDAY10ARQBPQRCRPDPQREPQRFRQP20AIFIAMTOREMEMBERTOSENDYOUTHEADDRESS,THENYOUWILLHAVETOSENDMEANEMAILMESSAGETHISHASBEENSLIGHTLYREWORDEDSOTHATTHETENSESMAKEMORESENSEBIFYOUWEREBORNINTHEUNITEDSTATES,THENYOUAREACITIZENOFTHISCOUNTRYCIFYOUKEEPYOURTEXTBOOK,THENITWILLBEAUSEFULREFERENCEINYOURFUTURECOURSESTHEWORD“THEN“ISUNDERSTOODINENGLISH,EVENIFOMITTEDDIFTHEIRGOALTENDERPLAYSWELL,THENTHEREDWINGSWILLWINTHESTANLEYCUPEIFYOUGETTHEJOB,THENYOUHADTHEBESTCREDENTIALSFIFTHEREISASTORM,THENTHEBEACHERODESGIFYOULOGONTOTHESERVER,THENYOUHAVEAVALIDPASSWORDHIFYOUDONTBEGINYOURCLIMBTOOLATE,THENYOUWILLREACHTHESUMMIT33CPQRPQPRTTTTTTFTTFTTTFFTFTTTFTFTFFTTFFFTP26128AKWAMEWILLNOTTAKEAJOBININDUSTRYANDHEWILLNOTGOTOGRADUATESCHOOLBYOSHIKODOESNTKNOWJAVAORSHEDOESNTKNOWCALCULUSCJAMESISNOTYOUNGORHEISNOTSTRONGDRITAWILLNOTMOVETOOREGONANDSHEWILLNOTMOVETOWASHINGTON10APQPPQPPQPPQQTTFTFTTFFTFTFTTTTTFFTFFTCPQPQPPQPPQQTTTTTTFFFTFTTFTFFTFT12AASSUMETHEHYPOTHESISISTRUETHENPISFALSESINCEPQISTRUE,WECONCLUDETHATQMUSTBETRUEHEREISAMORE“ALGEBRAIC“SOLUTIONPPQQPPQQPPQQPPQQPQPQTCASSUMETHEHYPOTHESISISTRUETHENPISTRUE,ANDSINCETHESECONDPARTOFTHEHYPOTHESISISTURE,WECONCLUDETHATQISALSOTRUE,ASDESIRED24PQRPQPRPQPRQRPQRTTTTTTTTTTFTFTTTTFTFTTTTTFFFFFFFFTTTTTTTFTFTTTTTFFTTTTTTFFFTTTFT30PQRPQPRQRPQPRPQPRQRTTTTTTTTTTFTFTFTTFTTTTTTTFFTFFFTFTTTTTTTFTFTTTTTFFTFTTFTFFFFTFFT51PPQPPQ977THEGRAPHISPLANARADECFB20THEGRAPHISNOTHOMEOMORPHICTOK3,3,SINCEBYREROUTINGTHEEDGEBETWEENAANDHWESEETHATITISPLANAR22REPLACEEACHVERTEXOFDEGREETWOANDITSINCIDENTEDGESBYASINGLEEDGETHENTHERESULTISK3,3THEPARTSAREA,E,IANDC,G,KTHEREFORETHISGRAPHISHOMEOMORPHICTOK3,323THEGRAPHISPLANAR25THEGRAPHISNOTPLANAR9833AFBCED839210417TIMESLOT1MATH115,MATH185TIMESLOT2MATH116,CS473TIMESLOT3MATH195,CS101TIMESLOT4CS102TIMESLOT5CS273P46133ATRUEBFALSECFALSEDFALSE5ATHEREISASTUDENTWHOSPENDSMORETHAN5HOURSEVERYWEEKDAYINCLASSBEVERYSTUDENTSPENDSMORETHAN5HOURSEVERYWEEKDAYINCLASSCTHEREISASTUDENTWHODOESNOTSPENDMORETHAN5HOURSEVERYWEEKDAYINCLASSDNOSTUDENTSPENDSMORETHAN5HOURSEVERYWEEKDAYINCLASS9AXPXQXBXPXQXCXPXQXDXPXQX16ATRUEBFALSECTRUEDFALSE24LETCXBETHEPROPOSITIONALFUNCTION“XISINYOURCLASS”AXPXANDXCXPX,WHEREPXIS“XHASACELLULARPHONE”BXFXANDXCXFX,WHEREFXIS“XHASSEENAFOREIGNMOVIE”CXSXANDXCXSX,WHERESXIS“XCANSWIM”DXEXANDXCXEX,WHEREEXIS“XCANSOLVEQUADRATICEQUATIONS”EXRXANDXCXRX,WHERERXIS“XWANTSTOBERICH”62AXPXSXBXRXSXCXQXPXDXQXRXEYESIFXISONEOFMYPOULTRY,THENHEISADUCKBYPARTC,HENCENOTWILLINGTOWALTZPARTASINCEOFFICERSAREALWAYSWILLINGTOWALTZPARTB,XISNOTANOFFICERP591412DXCX,BOBHXYIXXYIYKXYIXCX,YNXYZXYCX,ZCY,Z14AXHX,WHEREHXIS“XCANSPEAKHINDI”ANDTHEUNIVERSEOFTHEDISCOURSECONSISTSOFALLSTUDENTSINTHISCLASSBXYPX,Y,WHEREPX,YIS“XPLAYSY”ANDTHEUNIVERSEOFTHEDISCOURSEFORXCONSISTSOFALLSTUDENTSINTHISCLASS,ANDTHEUNIVERSEOFTHEDISCOURSEFORYCONSISTSOFALLSPORTSCXAXHX,WHEREAXIS“XHASVISITEDALASKA”,HXIS“XHASVISITEDHAWAII”ANDTHEUNIVERSEOFTHEDISCOURSEFORXCONSISTSOFALLSTUDENTSINTHISCLASSDXYLX,Y,WHERELX,YIS“XHASLEARNEDPROGRAMMINGLANGUAGEY”ANDTHEUNIVERSEOFTHEDISCOURSEFORXCONSISTSOFALLSTUDENTSINTHISCLASS,ANDTHEUNIVERSEOFTHEDISCOURSEFORYCONSISTSOFALLPROGRAMMINGLANGUAGESEXZYQY,ZPX,Y,WHEREPX,YIS“XHASTAKENCOURSEY”,QY,ZIS“COURSEYISOFFEREDBYDEPARTMENTZ”,ANDTHEUNIVERSEOFTHEDISCOURSEFORXCONSISTSOFALLSTUDENTSINTHISCLASS,THEUNIVERSEOFTHEDISCOURSEFORYCONSISTSOFALLCOURSESINTHISSCHOOL,ANDTHEUNIVERSEOFTHEDISCOURSEFORZCONSISTSOFALLDEPARTMENTSINTHISSCHOOLFXYZXYPX,YXYZPX,Z,WHEREPX,YIS“XANDYGREWUPINTHESAMETOWN”ANDTHEUNIVERSEOFTHEDISCOURSEFORX,Y,ZCONSISTSOFALLSTUDENTSINTHISCLASSGXYZCX,YGY,Z,WHERECX,YIS“XHASCHATTEDWITHY”,GY,ZIS“YISINCHATGROUPZ”,THEUNIVERSEOFTHEDISCOURSEFORX,YCONSISTSOFALLSTUDENTSINTHISCLASS,ANDTHEUNIVERSEOFTHEDISCOURSEFORZCONSISTSOFALLCHATGROUPINTHISCLASS24ATHEREISANADDITIVEIDENTITYFORTHEREALNUMBERSDTHEPRODUCTOFTWONONZERONUMBERSISNONZEROFORTHEREALNUMBERS38BTHEREARENOSTUDENTSINTHISCLASSWHOHAVENEVERSEENACOMPUTERDTHEREARENOSTUDENTSINTHISCLASSWHOHAVETAKENBEENINATLEASTONEROOMOFEVERYBUILDINGONCAMPUS151RQPPQRRQPPQRQPPQRPQRQPQRPPQR30,1,2,4,5,6,72P726LETRBETHEPROPOSITION“ITRAINS“,LETFBETHEPROPOSITION“ITISFOGGY“,LETSBETHEPROPOSITION“THESAILINGRACEWILLBEHELD“,LETLBETHEPROPOSITION“THELIFESAVINGDEMONSTRATIONWILLGOON“,ANDLETTBETHEPROPOSITION“THETROPHYWILLBEAWARDED“WEAREGIVENPREMISESRFSL,ST,ANDTWEWANTTOCONCLUDERWESETUPTHEPROOFINTWOCOLUMNS,WITHREASONSNOTETHATITISVALIDTOREPLACESUBEXPRESSIONSBYOTHEREXPRESSIONSLOGICALLYEQUIVALENTTOTHEMSTEPREASON1THYPOTHESIS2STHYPOTHESIS3SMODUSTOLLENSUSINGSTEPS1AND24RFSLHYPOTHESIS5SLRFCONTRAPOSITIVEOFSTEP46SLRFDEMORGANSLAWANDDOUBLENEGATIVE7SLADDITION,USINGSTEP38RFMODUSPONENSUSINGSTEP6AND79RSIMPLIFICATIONUSINGSTEP812FIRST,USINGTHECONCLUSIONOFEXERCISE11,WESHOULDSHOWTHATTHEARGUMENTFORMWITHPREMISESPTRS,QUT,UP,S,Q,ANDCONCLUSIONRISVALIDTHEN,WEUSERULESOFINFERENCEFROMTABLE1STEPREASON1QPREMISE2QUTPREMISE3UTMODUSPONENSUSINGSTEPS1AND24USIMPLIFICATIONUSINGSTEP35UPPREMISE6PMODUSPONENSUSINGSTEPS3AND47TSIMPLIFICATIONUSINGSTEP38PTCONJUNCTIONUSINGSTEPS6AND79PTRSPREMISE10RSMODUSPONENSUSINGSTEPS8AND911SPREMISE12RDISJUNCTIVESYLLOGISMUSINGSTEPS10AND1114BLETRXBE“XISONEOFTHEFIVEROOMMATES,”DXBE“XHASTAKENACOURSEINDISCRETEMATHEMATICS,”ANDAXBE“XCANTAKEACOURSEINALGORITHMS”THEPREMISESAREXRXDX,XDXAXANDRMELISSAUSINGTHEFIRSTPREMISEANDUNIVERSALINSTANTIATION,RMELISSADMELISSAFOLLOWSUSINGTHETHIRDPREMISEANDMODUSPONENS,DMELISSAFOLLOWSUSINGTHESECONDPREMISEANDUNIVERSALINSTANTIATION,AMELISSAFOLLOWSSODOTHEOTHERROOMMATESDLETCXBE“XISINTHECLASS,”FXBE“XHASBEENTOFRANCE,”ANDLXBE“XHASVISITEDLOUVRE”THEPREMISESAREXCXFXANDXFXLXFROMTHEFIRSTPREMISEANDEXISTENTIALINSTANTIATIONIMPLYTHATCYFYFORAPARTICULARPERSONYUSINGSIMPLIFICATION,FYFOLLOWSUSINGTHESECONDPREMISEANDUNIVERSALINSTANTIATIONFYLYFOLLOWSUSINGMODUSPONENS,LYFOLLOWSUSINGEXISTENTIALGENERALIZATION,XCXLXFOLLOWS24THEERRORSOCCURINSTEPS3,5AND7FORSTEPS3AND5,WECANNOTASSUME,ASISBEINGDONEHERE,THATTHECTHATMAKESPXTRUEISTHESAMEASTHECTHATMAKESQXTRUEATTHESAMETIMEFORSTEP7,ITISNOTACONJUNCTIONANDTHEREISNOSUCHDISJUNCTIONRULE29STEPREASON1XPXPREMISE2PCEXISTENTIALINSTANTIATIONFROM13XPXQXPREMISE4PCQCUNIVERSALINSTANTIATIONFROM35QCDISJUNCTIVESYLLOGISMFROM2AND46XQXSXPREMISE7QCSCUNIVERSALINSTANTIATIONFROM68SCDISJUNCTIVESYLLOGISMFROM5AND79XRXSXPREMISE10RCSCUNIVERSALINSTANTIATIONFROM911RCMODUSTOLLENSFROM8AND1012XRXEXISTENTIALGENERALIZATIONFROM11P861637SUPPOSETHATP1P4P2P5P3P1TOPROVETHATONEOFTHESEPROPOSITIONSIMPLIESANYOFTHEOTHERS,JUSTUSEHYPOTHETICALSYLLOGISMREPEATEDLYP1031713ATHISSTATEMENTASSERTSTHEEXISTENCEOFXWITHACERTAINPROPERTYIFWELETYX,THENWESEETHATPXISTRUEIFYISANYTHINGOTHERTHANX,THENPXISNOTTRUETHUS,XISTHEUNIQUEELEMENTTHATMAKESPTRUEBTHEFIRSTCLAUSEHERESAYSTHATTHEREISANELEMENTTHATMAKESPTRUETHESECONDCLAUSESAYSTHATWHENEVERTWOELEMENTSBOTHMAKEPTRUE,THEYAREINFACTTHESAMEELEMENTTOGETHERTHESESAYTHATPISSATISFIEDBYEXACTLYONEELEMENTCTHISSTATEMENTASSERTSTHEEXISTENCEOFANXTHATMAKESPTRUEANDHASTHEFURTHERPROPERTYTHATWHENEVERWEFINDANELEMENTTHATMAKESPTRUE,THATELEMENTISXINOTHERWORDS,XISTHEUNIQUEELEMENTTHATMAKESPTRUEP120219TTFTTF16SINCETHEEMPTYSETISASUBSETOFEVERYSET,WEJUSTNEEDTOTAKEASETBTHATCONTAINSASANELEMENTTHUSWECANLETAANDBASTHESIMPLESTEXAMPLE20THEUNIONOFTHESETSINTHEPOWERSETOFASETXMUSTBEEXACTLYXINOTHERWORDS,WECANRECOVERXFROMITSPOWERSET,UNIQUELYTHEREFORETHEANSWERISYES22ATHEPOWERSETOFEVERYSETINCLUDESATLEASTTHEEMPTYSET,SOTHEPOWERSETCANNOTBEEMPTYTHUSISNOTTHEPOWERSETOFANYSETBTHISISTHEPOWERSETOFACTHISSETHASTHREEELEMENTSSINCE3ISNOTAPOWEROF2,THISSETCANNOTBETHEPOWERSETOFANYSETDTHISISTHEPOWERSETOFA,B28AA,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,1C0,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,YP1302214SINCEAABAB,WECONCLUDETHATA1,5,7,83,6,91,3,5,6,7,8,9SIMILARLYBBAAB2,103,6,92,3,6,9,1024FIRSTSUPPOSEXISINTHELEFTHANDSIDETHENXMUSTBEINABUTINNEITHERBNORCTHUSXAC,BUTXBC,SOXISINTHERIGHTHANDSIDENEXTSUPPOSETHATXISINTHERIGHTHANDSIDETHUSXMUSTBEINACANDNOTINBCTHEFIRSTOFTHESEIMPLIESTHATXAANDXCBUTNOWITMUSTALSOBETHECASETHATXB,SINCEOTHERWISEWEWOULDHAVEXBCTHUSWEHAVESHOWNTHATXISINABUTINNEITHERBNORC,WHICHIMPLIESTHATXISINTHELEFTHANDSIDE40THISISANIDENTITYEACHSIDECONSISTSOFTHOSETHINGSTHATAREINANODDNUMBEROFTHESETSA,B,ANDCP1472335ATHISREALLYHASTWOPARTSFIRSTSUPPOSETHATBISINFSTTHUSBFAFORSOMEASTEITHERAS,INWHICHCASEBFS,ORAT,INWHICHCASEBFTTHUSINEITHERCASEBFSFTTHISSHOWSTHATFSTFSFT,CONVERSELY,SUPPOSEBFSFTTHENEITHERBFSORBFTTHISMEANSEITHERTHATBFAFORSOMEASORTHATBFAFORSOMEATINEITHERCASE,BFAFORSOMEAST,SOBFSTTHISSHOWSTHATFSFTFST,ANDOURPROOFISCOMPLETEBSUPPOSEBFSTTHENBFAFORSOMEASTTHISIMPLIESTHATASANDAT,SOWEHAVEBFSANDBFTTHEREFOREBFSFT,ASDESIRED52INSOMESENSETHISQUESTIONISITSOWNANSWERTHENUMBEROFINTEGERSBETWEENAANDB,INCLUSIVE,ISTHENUMBEROFINTEGERSBETWEENAANDB,INCLUSIVEPRESUMABLYWESEEKANEXPRESSINVOLVINGA,B,ANDTHEFLOORAND/ORCEILINGFUNCTIONTOANSWERTHISQUESTIONIFWEROUNDAUPANDROUNDBDOWNTOINTEGERS,THENWEWILLBELOOKINGATTHESMALLESTANDLARGESTINTEGERSJUSTINSIDETHERANGEOFTHEINTEGERSWEWANTTOCOUNT,RESPECTIVELYTHESEVALUESAREOFCOURSEAND,RESPECTIVELYTHENTHEANSWERISB1JUSTTHINKOFCOUNTINGALLTHEINTEGERSBETWEENTHESETWOVALUES,ABINCLUDINGBOTHENDSIFAROWOFFENCEPOSTSONEFOOTAPARTEXTENDSFORKFEET,THENTHEREAREK1FENCEPOSTSNOTETHATTHISEVENWORKSWHEN,FOREXAMPLE,A03ANDB07P1622434ATHISISCOUNTABLETHEINTEGERSINTHESETARE1,2,4,5,7,ANDSOONWECANLISTTHESENUMBERSINTHEORDER1,1,2,2,4,4,THEREBYESTABLISHINGTHEDESIREDCORRESPONDENCEINOTHERWORDS,THECORRESPONDENCEISGIVENBY11，21，32，42，54，ANDSOONBTHISISSIMILARTOPARTAWECANSIMPLYLISTTHEELEMENTSOFTHESETINORDEROFINCREASINGABSOLUTEVALUE,LISTINGEACHPOSITIVETERMBEFOREITSCORRESPONDINGNEGATIVE5,5,10,10,15,15,20,20,30,30,40,40,45,45,50,50,CTHISISCOUNTABLEBUTALITTLETRICKYWECANARRANGETHENUMBERSINA2DIMENSIONALTABLEASFOLLOWS11011011101111011111111111111111111111111111111111111111111111111111111111111111111DTHISSETISNOTCOUNTABLEWECANPROVEITBYTHESAMEDIAGONALIZATIONARGUMENTASWASUSEDTOPROVETHATTHESETOFALLREALSISUNCOUNTABLEINEXAMPLE21ALLWENEEDTODOISCHOOSEDI1WHENDII9ANDCHOOSEDI9WHENDII1ORDIIISBLANKIFTHEDECIMALEXPANSIONISFINITE46WEKNOWFROMEXAMPLE21THATTHESETOFREALNUMBERSBETWEEN0AND1ISUNCOUNTABLELETUSASSOCIATETOEACHREALNUMBERINTHISRANGEINCLUDING0BUTEXCLUDING1AFUNCTIONFROMTHESETOFPOSITIVEINTEGERSTOTHESET0,1,2,3,4,5,6,7,8,9ASFOLLOWSIFXISAREALNUMBERWHOSEDECIMALREPRESENTATIONIS0D1D2D3WITHAMBIGUITYRESOLVEDBYFORBIDDINGTHEDECIMALTOENDWITHANINFINITESTRINGOF9S,THENWEASSOCIATETOXTHEFUNCTIONWHOSERULEISGIVENBYFNDNCLEARLYTHISISAONETOONEFUNCTIONFROMTHESETOFREALNUMBERSBETWEEN0AND1ANDASUBSETOFTHESETOFALLFUNCTIONSFROMTHESETOFPOSITIVEINTEGERSTHESET0,1,2,3,4,5,6,7,8,9TWODIFFERENTREALNUMBERSMUSTHAVEDIFFERENTDECIMALREPRESENTATIONS,SOTHECORRESPONDINGFUNCTIONSAREDIFFERENTAFEWFUNCTIONSARELEFTOUT,BECAUSEOFFORBIDDINGREPRESENTATIONSSUCHAS0239999SINCETHESETOFREALNUMBERSBETWEEN0AND1ISUNCOUNTABLE,THESUBSETOFFUNCTIONSWEHAVEASSOCIATEDWITHTHEMMUSTBEUNCOUNTABLEBUTTHESETOFALLSUCHFUNCTIONSHASATLEASTTHISCARDINALITY,SOIT,TOO,MUSTBEUNCOUNTABLEP191321THECHOICESOFCANDKARENOTUNIQUEAYESC1,K10BYESC4,K7CNODYESC5,K1EYESC1,K0FYESC1,K29X24X173X3FORALLX17,SOX24X17ISOX3,WITHWITNESSESC3,K17HOWEVER,IFX3WEREOX24X17,THENX3CX24X173CX2FORSOMEC,FORALLSUFFICIENTLYLARGEX,WHICHIMPLIESTHATX3C,FORALLSUFFICIENTLYLARGEX,WHICHISIMPOSSIBLEP2093419ANOBNOCYESDNO31AGRQRWSDVVJRBQBABGCNFFTBCQXUXMAHJJZXP2183513AYESBNOCYESDYES17A2B4C12P2804122ALITTLECOMPUTATIONCONVINCESUSTHATTHEANSWERISTHATN2NFORN0,1,ANDALLN4CLEARLYTHEINEQUALITYDOESNTHOLDFORN2ORN3WEWILLPROVEBYMATHEMATICALINDUCTIONTHATTHEINEQUALITYHOLDSFORALLN4THEBASECASEISCLEAR,SINCE1624NOWSUPPOSETHATN2NFORAGIVENN4WEMUSTSHOWTHATN12N1EXPANDINGTHELEFTHANDSIDE,APPLYINGTHEINDUCTIVEHYPOTHESIS,ANDTHENINVOKINGSOMEVALIDBOUNDSSHOWSTHISN22N1N2N1N2N1N3NNNNNNNN1NN1P2934231ASSUMETHATTHEWELLORDERINGPROPERTYHOLDSSUPPOSETHATP1ISTRUEANDTHATTHECONDITIONALSTATEMENTP1P2PNPN1ISTRUEFOREVERYPOSITIVEINTEGERNLETSBETHESETOFPOSITIVEINTEGERSNFORWHICHPNISFALSEWEWILLSHOWSASSUMETHATS,THENBYTHEWELLORDERINGPROPERTYTHEREISALEASTINTEGERMINSWEKNOWTHATMCANNOTBE1BECAUSEP1ISTRUEBECAUSENMISTHELEASTINTEGERSUCHTHATPNISFALSE,P1,P2,PM1ARETRUE,ANDM11BECAUSEP1P2PM1PMISTRUE,ITFOLLOWSTHATPMMUSTALSOBETRUE,WHICHISACONTRADICTIONHENCE,SP3084310THEBASECASEISTHATSM0MTHERECURSIVEPARTISTHATSMN1ISTHESUCCESSOROFSMNIE,SMN112THEBASECASEN1ISCLEAR,SINCEF12F1F21ASSUMETHEINDUCTIVEHYPOTHESISTHENF12F22FN2FN12FN12FNFN1FN1FN1FNFN1FN2,ASDESIRED31IFXISASETORVARIABLEREPRESENTINGSET,THENXISWELLFORMEDFORMULAIFXANDYAREALLWELLFORMEDFORMULAS,THEN,XY,XYANDXYAREALLWELLFORMEDXFORMULAS50LETPNBE“A1,N2N”BASICSTEPP1ISTRUE,BECAUSEP1A1,1221INDCUTIVESTEPASSUMETHATPMISTRUE,THATISA1,M2MANDM1THENPM1A1,M1A0,A1,MA0,2M22M2M1SOA1,N2NWHENEVERN159BNOTWELLDEFINEDF2ISNOTDEFINEDSINCEF0ISNTALSO,F2ISAMBIGUOUSDNOTWELLDEFINEDTHEDEFINITIONISAMBIGUOUSABOUTN1P344513A104B512WEUSETHESUMRULE,ADDINGTHENUMBEROFBITSTRINGSOFEACHLENGTHUPTO6IFWEINCLUDETHEEMPTYSTRING,THENWEGET2021222324252627112720AEVERYSEVENTHNUMBERISDIVISIBLEBY7THEREFORETHEREARE999/7142SUCHNUMBERSNOTETHATWEUSETHEFLOORFUNCTION,BECAUSETHEKTHMULTIPLEOF7DOESNOTOCCURUNTILTHENUMBER7KHASBEENREACHEDBFORSOLVINGTHISPARTANDTHENEXTFOURPARTS,WENEEDTOUSETHEPRINCIPLEOFINCLUSIONEXCLUSIONJUSTASINPARTA,THEREARE999/1190NUMBERSINOURRANGEDIVISIBLEBY11,ANDTHEREARE999/7712NUMBERSINOURRANGEDIVISIBLEBYBOTH7AND11THEMULTIPLESOF77ARETHENUMBERSWESEEKIFWETAKETHESE12NUMBERSAREAWAYFROMTHE142NUMBERSDIVISIBLEBY7,WESEETHATTHEREARE130NUMBERSINOURRANGEDIVISIBLEBY7BUTNOTBY11CASEXPLAINEDINPARTB,THEANSWERIS12DBYTHEPRINCIPLEOFINCLUSIONEXCLUSION,THEANSWER,USINGTHEDATAFROMPARTB,IS1429012220EIFWESUBTRACTFROMTHEANSWERTOPARTDTHENUMBEROFNUMBERSDIVISIBLEBYNEITHEROFTHEMSOTHEANSWERIS22012208FIFWESUBTRACTTHEANSWERTOPARTDFROMTHETOTALNUMBEROFPOSITIVEINTEGERSLESSTHAN1000,WEWILLHAVETHENUMBEROFNUMBERSDIVISIBLEBYEXACTLYONEOFTHEMSOTHEANSWERIS999220779GIFWEASSUMETHATNUMBERSAREWRITTENWITHOUTLEADING0S,THENWESHOULDBREAKTHEPROBLEMDOWNINTOTHREECASESONEDIGITNUMBERS,TWODIGITNUMBERSCLEARLYTHEREARE9ONEDIGITNUMBERS,ANDEACHOFTHEMHASDISTINCTDIGITSTHEREARE90TWODIGITNUMBERS10THROUGH99,ANDALLBUT9OFTHEMHAVEDISTINCTDIGITSANALTERNATIVEWAYTOCOMPUTETHISISTONOTETHATTHEFIRSTDIGITMUSTBE1THROUGH99CHOICESANDTHESECONDDIGITMUSTBESOMETHINGDIFFERENTFROMTHEFIRSTDIGIT9CHOICESOUTOFTHE10POSSIBLEDIGITS,SOBYTHEPRODUCTRULE,WEGET9981CHOICESINALLTHISAPPROACHALSOTELLSUSTHATTHEREARE998648THREEDIGITNUMBERSWITHDISTINCTDIGITSAGAIN,WORKFROMLEFTTORIGHTINTHEONESPLACE,ONE8DIGITSARELEFTTOCHOOSEFROM80THEFINALANSWERIS981648738HITTURNSOUTTOBEEASIERTOCOUNTTHEODDNUMBERSWITHDISTINCTDIGITSANDSUBTRACTFROMOURANSWERTOPARTG,SOLETUSPROCEEDTHATWAYTHEREARE5ODDONEDIGITNUMBERSFORTWODIGITNUMBERS,FIRSTCHOOSETHEONEDIGIT5CHOICES,THENCHOOSETHETENSDIGITS8CHOICES,SINCENEITHERTHEONESDIGITVALUENOT0ISAVAILABLETHEREFORETHEREARE40SUCHTWODIGITNUMBERSNOTETHATTHISISNOTEXACTLYHALFOF81FORTHETHREEDIGITNUMBERS,FIRSTCHOOSETHEONESDIGIT5CHOICES,THENTHEHUNDREDSDIGIT8CHOICES,THENTHETENSDIGIT8CHOICES,GIVINGUS320INALLSOTHEREARE540320365ODDNUMBERSWITHDISTINCTDIGITSTHUSTHEFINALANSWERIS73836537335A若N1,为2；若N2,为2若N3,为0B对于N1,为；若N1,为1；NC2N1注N可映射到0，1两种可能44FIRSTWECOUNTTHENUMBEROFBITSTRINGSOFLENGTH10THATCONTAINFIVECONSECUTIVE0SWEWILLBASETHECOUNTONWHERETHESTRINGOFFIVEORMORECONSECUTIVE0SSTARTSIFITSTARTSINTHEFIRSTBIT,THENTHEFIRSTFIVEBITSAREALL0S,BUTTHEREISFREECHOICEFORTHELASTFIVEBITSTHEREFORETHEREARE2532SUCHSTRINGSIFITSTARTSINTHESECONDBIT,THENTHEFIRSTBITMUSTBEA1,THENEXTFIVEBITSAREALL0S,BUTTHEREISFREECHOICEFORTHELASTFOURBITSTHEREFORETHEREARE2416SUCHSTRINGSIFITSTARTSINTHETHIRDBIT,THENTHESECONDBITMUSTBEA1BUTTHEFIRSTBITANDTHELASTTHREEBITSAREARBITRARYTHEREFORETHEREARE2416SUCHSTRINGSSIMILARLY,THEREARE16SUCHSTRINGSTHATHAVETHECONSECUTIVE0SSTARTINGINEACHOFPOSITIONSFOUR,FIVE,ANDSIXTHISGIVESUSATOTALOF32516112STRINGSTHATCONTAINFIVECONSECUTIVE0SSYMMETRICALLY,THEREARE112STRINGSTHATCONTAINFIVECONSECUTIVE1SCLEARLYTHEREAREEXACTLYTWOSTRINGSTHATCONTAINBOTH0000011111,1111100000THEREFOREBYTHEINCLUSIONEXCLUSIONPRINCIPLE,THEANSWERIS2112222252WEDRAWTHETREE,WITHITSROOTATTHETOPWESHOWABRANCHFOREACHOFTHEPOSSIBILITIES0AND1,FOREACHBITINORDER,EXCEPTTHATWEDONOTALLOWTHREECONSECUTIVE0SSINCETHEREARE13LEAVES,THEANSWERIS1310FIRSTBIT1010SECONDBIT1010101THIRDBIT1010101101010FOURTHBITP353526THEREAREONLYDPOSSIBLEREMAINDERSWHENANINTEGERISDIVIDEDBYD,NAMELY0,1,D1BYTHEPIGEONHOLEPRINCIPLE,IFWEHAVED1REMAINDERS,THENATLEASTTWOMUSTBETHESAME10THEMIDPOINTOFTHESEGMENTWHOSEENDPOINTSAREA,BANDC,DISAC/2,BD/2WEARECONCERNEDONLYWITHINTEGERVALUESOFTHEORIGINALCOORDINATESCLEARLYTHECOORDINATESOFTHESEFRACTIONSWILLBEINTEGERSASWELLIFANDONLYIFAANDCHAVETHESAMEPARITYBOTHODDORBOTHEVENANDBANDDHAVETHESAMEPARITYTHUSWHATMATTERSINTHISPROBLEMISTHEPARITIESOFCOORDINATESTHEREAREFOURPOSSIBLEPAIRSOFPARITIESODD,ODD,ODD,EVEN,EVEN,EVENANDEVEN,ODDSINCEWEAREGIVENFIVEPOINTS,THEPIGEONHOLEPRINCIPLEGUARANTEESTHATATLEASTTWOOFTHEMWILLHAVETHESAMEPAIROFPARTIESTHEMIDPOINTOFTHESEGMENTJOININGTHESETWOPOINTSWILLTHEREFOREHAVEINTEGERCOORDINATES38ATBTCT1A13ANAN1AN2AN3BTHEINITIALCONDITIONSAREA01,A11,ANDA22,SINCETHEREISONEWAYTOCLIMBNOSTAIRSDONOTHING,CLEARLYONLYONEWAYTOCLIMBONESTAIR,ANDTWOWAYSTOCLIMBTWOSTAIRSONESTEPTWICEORTWOSTEPSATONCENOTETHATTHERECURRENCERELATIONISTHESAMEASTHATFOREXERCISE25CEACHTERMINOURSEQUENCEANISTHESUMOFTHEPREVIOUSTHREETERMS,SOTHESEQUENCEBEGINSA11,A22,A34,A47,A513,A624,A744,A881THUSAPERSONCANCLIMBAFLIGHTOF8STAIRSIN81WAYSUNDERTHERESTRICTIONSINTHISPROBLEM42LETANBETHENUMBEROFCOVERINGSAWEFOLLOWTHEHINTIFTHERIGHTMOSTDOMINOISPOSITIONEDVERTICALLY,THENWEHAVEACOVERINGOFTHELEFTMOSTN1COLUMNS,ANDTHISCANBEDONEINAN1WAYSIFTHERIGHTMOSTDOMINOISPOSITIONEDHORIZONTALLY,THENTHEREMUSTBEANOTHERDOMINODIRECTLYBENEATHIT,ANDTHESETOGETHERCOVERTHELASTTWOCOLUMNSTHEFIRSTN2COLUMNSTHEREFOREWILLNEEDTOCONTAINACOVERINGBYDOMINOS,ANDTHISCANBEDONEINAN2WAYSTHUSWEOBTAINTHEFIBONACCIRECURRENCEANAN1AN2BCLEARLYA11ANDA22CTHESEQUENCEWEOBTAINISJ