组合数学英文原文

1PigeonholePrinciple:SimpleformTheorem1.1.Ifn1objectsareputintonboxes,thenatleastoneboxcontainstwoormore

objects.

Proof.Trivial.

Example1.1.Among13peopletherearetwowhohavetheirbirthdaysinthesamemonth.

nn.2.Therearemarriedcouples.Howmanyofthe2peoplemustbeselectedinExample1

ordertoguaranteethatonehasselectedamarriedcouple?Otherprinciplesrelatedtothepigeonholeprinciple:

nnobjectsareputintoboxesandnoboxisempty,theneachboxcontainsexactlyone,If

object.

nn,Ifobjectsareputintoboxesandnoboxgetsmorethanoneobject,theneachboxhas

anobject.

Theabstractformulationofthethreeprinciples:LetandbefinitesetsandletYX

fXY:,beafunction.

,Ifhasmoreelementsthan,thenfisnotone-to-one.YX

,Ifandhavethesamenumberofelementsandfisonto,thenfisone-to-one.YX

,Ifandhavethesamenumberofelementsandfisone-to-one,thenfisonto.YX

Example1.3.Inanygroupofnpeoplethereareatleasttwopersonshavingthesamenumber

xxfriends.(Itisassumedthatifapersonisafriendofthenisalsoafriendof.)yy

xProof.Thenumberoffriendsofapersonisanintegerwith.Ifthereisa01,,,knk

personwhosenumberoffriendsis,theneveryoneisafriendof,thatis,noonehasyyn,1

aaa,,,0friend.Thismeansthat0andcannotbesimultaneouslythenumbersofkkk1211，，n

friendsofsomepeopleinthegroup.Thepigeonholeprincipletellsusthatthereareatleasttwo

peoplehavingthesamenumberoffriends.

aaa,,,nintegers,notnecessarilydistinct,thereexistintegersExample1.4.Givenk12n

nandwith<suchthatthesumisamultipleof.0,kll,n

nProof.Considertheintegers

aaaaaaaaa,,,,，，，，，11212312n

nDividingtheseintegersby,wehave

aaaqnr，，，,，,01,,,rnin,1,2,,12iiii

rrr,,,r,0aaa，，，Ifoneoftheremaindersiszero,say,,thenisamultiple12nk12k

rrr,,,11,,,rnnof.Ifnoneofiszero,thentwoofthemmustthesame(sincefor12ni

rr,aaa，，，all),say,with<.Thismeansthatthetwointegersandkliki12k

aaa，，，aaa，，，havethesameremainder.Thusisamultipleofn.kkl，，1212l

Example1.5.Achessmasterwhohas11weekstoprepareforatournamentdecidestoplayatleastonegameeverydaybut,inordernottotirehimself,hedecidesnottoplaymorethan12gamesduringanycalendarweek.

Showthatthereexistsasuccessionofconsecutivedaysduringwhichthechessmasterwillhaveplayedexactly21

games.

aabethenumberofgamesplayedonthefirstday,thetotalnumberofgamesProof.Let12

athetotalnumbergamesplayedonthefirst,second,andplayedonthefirstandseconddays,3

thirddays,andson.Sinceatleastonegameisplayedeachday,thesequenceof

,,aaaaaanumbers,isstrictlyincreasing,thatis,<<<.77121277

a,1Moreover,andsinceatmost12gamesareplayedduringanyoneweek,1

a,，,1211132Thus77

aaa<<<.1,,1321277

aaa，，，21,21,,21Notethatthesequenceisalsostrictlyincreasing,and1277

a，21a，21a，21<<<22,,，,1

Nowconsiderthe154numbers

,,aaaa，，，21,21,,21aa,,;77127712

eachofthemisbetween1and153.Itfollowsthattwoofthemmustbeequal.Since

,,aaaa，，，21,21,,21aa,aredistinctandarealsodistinct,thenthetwo77127712

aaequalnumbersmustbeoftheformsand，21ii

aaSincethenumbergamesplayeduptotheithdayis=,weconcludethatonthedays，21ii

jji，，1,2,,thechessmasterplayedatotalof21games.

1,2,,200Example1.6.Given101integersfromthereareatleasttwointegerssuchthatoneofthemisdivisiblebytheother.

Proof.Byfactoringoutasmany2'saspossible,weseethatanyintegercanbewrittenintheformk2,a,whereandaisodd.Thenumberacanbeoneofthe100numbersk,0

Thusamongthe101integerschosen,twoofthemmusthavethesamea'swhenthey1,3,,199

rsarewrittenintheform,say,andwith.Ifr<s,thenthefirstonedividesthe2,a2,ars,

second.Ifr>s,thenthesecondonedividesthefirstExample1.7(ChinesRemainderTheorem).Letmandnberelativelyprimepositiveintegers.

,xam,mod，，,hasasolution.Thenthesystem,ybn,mod，，,,

mnProof.Wemayassumethat<and<.Letusconsiderthenintegers0,a0,b

amamanma,,2,,1，，,，，，

mEachoftheseintegershasremainderawhendividedby.Supposethattwoofthemhadthe

rnsameremainderwhendividedby.Letthetwonumbersbeand,wherejma，ima，

qq<.Thenthereareintegersandsuchthatjn,,10,iji

qnr，qnr，=and=jma，ima，ji

Subtractingthefirstequationfromthesecond,wehave

=qqn,jim,，，，，ji

Sincegcd=1,weconcludethatnji,Notethat0<jin,,,1Thisisamn,，，，，

ncontradiction.Thustheintegershavedistinctamamanma,,2,,1，，,，，，

nnremainderswhendividedby0,1,2,,1n,.Thatis,eachofthenumbersoccurasaremainder.Inparticular,thenumberdoes.Letbetheintegerwithpb

n01,,,pnsuchthatthenumberhasremainderbwhendividedby.Thenxpma,，

xxqnb,，qnb，forsomeinteger,.So=andhastherequiredproperty.xpma,，q

2PigeonholePrinciple:StrongForm

qqq,,,Theorem2.1.Letbepositiveintegers.If12n

qqqn，，，,，112n

nqobjectsareputintoboxes,theneitherthe1stboxcontainsatleastobjects,orthe2ndbox1

qqcontainsatleastobjects,,thenthboxcontainsatleastobjects.2n

q,1Proof.Supposeitisnottrue,thatis,thethboxcontainsatmostobjects,=iii

n.Thenthetotalnumberofobjectscontainedintheboxescanbeatmost1,2,,n

,qqqn，，，,qqq,，,，，,111，，，，，，12n12n

whichisonelessthanthenumberofobjectsdistributed.Thisisacontradiction.Thesimpleformofthepigeonholeprincipleisobtainedfromthestrongformbytakingqqq,,,,212n

Then

qqqn，，，,1==21nn,，n，112n

Inelementarymathematicsthestrongformofthepigeonholeprincipleismostoftenappliedinthe

qqqr,,,,specialcasewhen.Inthiscasetheprinciplebecomes:12n

rn,Ifobjectsareputintoboxes,thenatleastoneoftheboxescontainsornr,，11，，

moreoftheobjects.

Equivalently,

aaa,,,n,Iftheaverageofnonnegativeintegersisgreaterthan,i.e.r,112n

aaa，，，12n>r,1n

rthenatleatsoneoftheintegersisgreaterthanorequalto.

Example2.1.Abasketoffruitisbeingarrangedoutofapples,bananas,andoranges.Whatisthesmallestnumberofpiecesoffruitthatshouldbeputinthebasketinordertoguaranteethateitherthereareatleast8applesoratleast6bananasoratleast9oranges?

,Answer:86931=21.

Example2.2.Giventwodisks,onesmallerthantheother.Eachdiskisdividedinto200congruentsectors.Inthelargerdisk100sectorsarechosenarbitrarilyandpaintedred;theother100sectorsarepaintedblue.Inthesmallerdiskeachsectorispaintedeitherredorbluewithnostipulationonthenumberofredandbluesectors.Thesmallerdiskisplacedonthelargerdisksothatthecentersandsectorscoincide.Showthatitispossibletoalignthetwodiskssothatthenumberofsectorsofthesmallerdiskwhosecolormatchesthecorrespondingsectorofthelargerdiskisatleast100.Proof.Wefixthelargerdiskfirstthenplacethesmallerdiskonthetopofthelargerdisksothatthecentersandsectorscoincide.There200waystoplacethesmallerdiskinsuchamanner.Foreachsuchalignment,somesectorsofthetwodisksmayhavethesamecolor.Sinceeachsectorofthesmallerdiskwillmatchthesamecolorsectorofthelargerdisk100timesamongallthe200waysandthereare200sectorsinthesmallerdisk,thetotalnumberofmatchedcolorsectors

10020020,000，,amongthe200waysisNotethatthereareonly200ways.Thenthereisat

20,000leastonewaythatthenumberofmatchedcolorsectorsis,100ormore.200

2aaa,,,Example2.3.Showthateverysequenceofn，1realnumberscontainseither212n，1

anincreasingsubsequenceoflengthoradecreasingsubsequenceoflength.n，1n，1Proof.Supposethereisnoincreasingsubse