UChicago Notes - Discrete Mathematics - Problems

《UChicago Notes - Discrete Mathematics - Problems》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、REU2011-ProblemsInstructor:LaszloBabaie-mail:laci@cs.uchicago.eduLastupdated:Monday,July11(Problems48-53added)1.(Balancingnumbers)Supposewehave13realnumberswiththefollowingproperty:ifweremoveanyoneofthenumbers,theremaining12canbesplitintotwosetsof6numberseachwithequalsum.Prove

2、:allthe13numbersareequal.(Hint:rstassumeallthenumbersareintegers.)[Caseofintegersdone07-07]2.~(Dividingarectangle)Alargerectangleiscutupintoanitenumberofsmallerrectangles.(Alledgesareeitherhorizontalorvertical.)Supposeeachofthesmallerrectangleshasatleastonesideofintegerlength.

3、Provethatthesameholdsforthelargerectangle.3.~(SpreadingInfection)Someofthe64cellsofachessboardareinitiallyinfected.Subsequentlytheinfectionspreadsaccordingtothefollowingrule:iftwoneighborsofacellareinfectedthenthecellgetsinfected.(Neighborsshareandedge,soeachcellhasatmostfournei

4、ghbors.)Nocellisevercured.Whatistheminimumnumberofcellsthatneedtobeinitiallyinfectedtoguaranteethattheinfectionspreadsalloverthechessboard?Itiseasytoseethat8aresucientinmanyways.Provethat7arenotenough.(ThisisanAH-HAproblem.Themainideaofaclearandconvincingsolutioncanbesummarized

5、inasingle9-letterword.)4.(Polynomialswithprimeexponents)Prove:everypolynomialf(x)6=0hasamultiplePg(x)=f(x)h(x)6=0inwhicheveryexponentisprime.(Sog(x)hastheformaxpppwherethesummationisoverprimes.)[Done:06-30]5.(Dominoes)Prove:ifweremovetwooppositecornersfromthechessboard,theboardc

6、annotbecoveredbydominoes.(Eachdominocoverstwoneighboringcellsoftheboard.)LookforanAH-HA"proof:brief,convincing,nocasestodistinguish.[Done:06-30]6.(Triominoes)Removeacornerfromannchessboard.Weattempttotiletheboardbytriominoes.(Atriominoislikeadominoexceptitcoversthreecellsinaro

7、worinacolumn.)Provethatnotilingexistswhenn1(mod3).(Ah-ha")[Done:06-30]7.(*Band-Aids*)Considerthreepairwiseadjacentfacesofannnncube.Forwhatvaluesofnisitpossibletotilethethreefaceswith31band-aids"?8.(Primepowersinbinomialcoecients)Prove:ifaprimepowerptdividesthebinomial
c

8、oecientnthenptn.kQ9.~(Productsofprimes)Prove,