浙江大学离散数学2015期末考试题(英文班)

DepartmentofInformationScienceandElectronicEngineeringZhejiangUniversityFinalExamination11193011DiscreteMathematicsAssoc.Prof.Dr.ThomasHonoldM.Sc.JingmeiAiFallSemester,2014Name:Matric.No.:Question123456PMarksObtainedMaximalMarks151515201520100Timeallowed:120minutesInstructionstocandidates:•Thisexaminationpapercontainssix(6)questions.•Pleaseanswereveryquestionandsubquestion,andjustifyyouranswers.•Foryouranswerspleaseusethespaceprovidedaftereachquestion.Ifthisspaceisinsucient,pleasecontinueontheblanksheetsprovided.•ThisisaCLOSEDBOOKexamination,exceptthatyoumaybring1sheetofA4paper(hand-writtenonly)andaChinese-Englishdictionary(papercopyonly)totheexamination.FinalExamination(A)11193011DiscreteMathematics(Prof.Honold)Nov20,20148.00{10.00Question1(15marks)a)Is(p1$p2)_p1atautology?b)Are(p1!p2)!p3andp1!(p2!p3)logicallyequivalent?c)Fermat'sLastTheorem(FLT)statesthattheequationxn+yn=znhasnointegersolutionwithxyz6=0andn3.ExpressFLTasaformulaofpredicatecalculuswithdomainZ.Note:Youmayusethebasicoperationsofordinaryarithmetic,includingpowers`xn'andthecomparisonoperators'=',''.Nofurtherabbreviationsareallowed.Thedomain(universeofdiscourse)mustbethesetofallintegers.Question2(15marks)Threeblackballs,threeredballsandthreeyellowballsarearrangedina33matrixinsuchawaythatthereisnomonochromaticroworcolumn(\monochro-maticreferstoballsofthesamecolor).Ballsofthesamecolorareconsideredasindistinguishable.Inhowmanywayscanthisbedone?Question3(15marks)Supposea1;a2;:::;a10areintegerssatisfying1a1a2


a1040.Showthatthereexistdistinct3-subsetsfi;j;kgandfr;s;tgoff1;2;:::;10gsuchthatai+aj+ak=ar+as+at:Question4(20marks)LetGbethesimplegraphwhoseverticesarethesubsetsSf1;2;3;4;5;6;7gwithjSj=3,twoverticesSandTbeingadjacentifandonlyifS\T=;.a)HowmanyverticesandedgesdoesGhave?b)IsGregular?Ifapplicable,determineitsdegree.c)IsGconnected?d)IsGbipartite?Question5(15marks)a)Findaparticularsolutionoftherecurrencerelationan=3an14an3+4n:Hint:Therecurrencerelationhasasolutionoftheforman=cn+d,wherec,dareconstants.b)Determinethegeneralsolutionoftherecurrencerelationina).Question6(20marks)Alista=(a0;a1;:::;an1)ofintegersissaidtohavea(contiguous)zerosubsumifthereexist0ijn1suchthatai+ai+1+


+aj=0.{1{FinalExamination(A)11193011DiscreteMathematics(Prof.Honold)Nov20,20148.00{10.00a)Write(usingaprogramminglanguageorsomeformofpseudocode)abooleanfunctionhaszerosubsum(a)withparameteraasabove,whichreturnstrueifahasazerosubsumandfalseotherwise.b)Determinetheworst-casetimecomplexityofyouralgorithm,usingadditionsandcomparisonsoflistelementsasbasicoperations.Boththeexactnumberofbasicoperationsandanasymptoticgrowthestimateshouldbegiven.c)Doesthereexistamoreecientalgorithmforthistask?Brieyjustifyyouranswer.{2{FinalExamination(A)11193011DiscreteMathematics(Prof.Honold)Nov20,20148.00{10.00Solutions1a)No.1Thiscanbeprovedeitherbyatruthtableor,e.g.,asfollows:Ifp1isfalseandp2istruethenp1$p2isfalse.Hencethedisjunction(p1$p2)_p1isfalseaswell.4b)No.1Fortheproofonecanuseagainatruthtableor,e.g.,thefollowingshorterargument:p1!(p2!p3)isfalseforexactlyoneassigmentoftruthvaluestop1;p2;p3,viz.p1=p2=T,p3=F.Ontheotherhand,(p1!p2)!p3isfalsewheneverp1=p3=F(sincep1!p2=Tinthiscase),andhenceforatleasttwoassigmentsoftruthvalues(infactforexactlythree).4c)Anappropriateformulais:9x9y9z9n:(xyz=0)^n3^(xn+yn=zn)
:5X1=152WriteAforthesetofallarrangementsofthe9balls(withoutanyrestriction)andAi(Bj)forthesetofarrangementswithrowi(resp.,columnj)monochromatic.ThenthedesirednumberisjAn(A1[A2[A3[B1[B2[B3)j.2WeusethePIEforthecomputation.ThenumberofunrestrictedarrangementsisjAj=93;3;3
=93
63
=84
20=1680.3FurtherwehavejAij=jBjj=363=60;2jAi;jj=jBi;jj=3!=6;2jA1;2;3j=jB1;2;3j=6;3since2monochromaticrowsforcethe3rdrowtobemonochromaticaswell.AllotherintersectionsbetweenthesetsAi,BjinvolveatleastoneAiandatleastoneBj.Sincemonochromaticrowsandcolumnsexcludeeachother,theseintersectionsareallempty.1Itfollowsthatthedesirednumberis16806
60+6
62
6=1344:2X2=153Thenumberofdistinct3-subsetsoff1;2;:::;10gis103=10
9
83
2
1=120:5{3{FinalExamination(A)11193011DiscreteMathematics(Prof.Honold)Nov20,20148.00{10.00The120sumsai+aj+akareintegersintherange[3;120].Thereare118suchintegers.5=)Bythepigeonholeprinciple,since120118,thesumscannotbedistinct.Hencethereexistatleasttwo3-subsetswiththesamesum.5X3=154a)ThenumberofverticesofGis73
=35.3ThenumberofedgesofGis73
43

12=70.Alternatively,useb)andtheformulae=vr2forthenumberofedgesofaregulargraph.)3b)Yes.Thedegreeofavertexfa;b;cgisthenumberof3-subsetsoff1;2;:::;7gnfa;b;cg,whichisa4-set.HenceGisregularofdegree43
=4.4c)Yes.Considertwonon-adjacentverticesSandT.ThenjS\Tj2f1;2g.1IfjS\Tj=2thenjS[Tj=4andS,Thaveacommonneighbor,viz.f1;2;:::;7gn(S[T).HenceSandTareconnectedbyapathoflength2.2IfjS\Tj=1,letw.l.o.g.S=f1;2;3g,T=f1;4;5g.Then,e.g.,M=f4;5;6gisadjacenttoS,N=f2;3;7gisadjacenttoT,andM,Nareadjacentaswell.HenceSandTareconnectedbyapathoflength3.2InallGisconnectedandhasdiameter3.d)No.Ghascyclesoflength7,viz.f1;2;3g!f4;5;6g!f7;1;2g!f3;4;5g!f6;7;1g!f2;3;4g!f5;6;7g!f1;2;3g3Sinc