20 pigeonhole-principle

ds

1. 1
The Pigeonhole
Principle
CS/APMA 202
Rosen section 4.2
Aaron Bloomfield

2. 2
The pigeonhole principle
Supposeaflockofpigeonsflyintoasetof
pigeonholestoroost
Iftherearemorepigeonsthanpigeonholes,then
theremustbeatleast1pigeonholethathas
morethanonepigeoninit
Ifk+1ormoreobjectsareplacedintokboxes,
thenthereisatleastoneboxcontainingtwoor
moreoftheobjects
ThisisTheorem1

3. 3
Pigeonhole principle examples
Inagroupof367people,theremustbe
twopeoplewiththesamebirthday
Asthereare366possiblebirthdays
Inagroupof27Englishwords,atleast
twowordsmuststartwiththesameletter
Asthereareonly26letters

4. 4
Generalized pigeonhole principle
IfNobjectsareplacedintokboxes,then
thereisatleastoneboxcontainingN/k
objects
ThisisTheorem2

5. 5
Generalized pigeonhole principle
examples
Among100people,thereareatleast
100/12=9bornonthesamemonth
Howmanystudentsinaclassmustthere
betoensurethat6studentsgetthesame
grade(oneofA,B,C,D,orF)?
The“boxes”arethegrades.Thus,k=5
Thus,wesetN/5=6
LowestpossiblevalueforNis26

6. 6
Rosen, section 4.2, question 4
Abowlcontains10redand10yellowballs
a)Howmanyballsmustbeselectedtoensure3ballsof
thesamecolor?
Onesolution:considerthe“worst”case
Consider2ballsofeachcolor
Youcan’ttakeanotherballwithouthitting3
Thus,theansweris5
Viageneralizedpigeonholeprinciple
Howmanyballsarerequiredifthereare2colors,andonecolor
musthave3balls?
Howmanypigeonsarerequiredifthereare2pigeonholes,and
onemusthave3pigeons?
numberofboxes:k=2
WewantN/k=3
WhatistheminimumN?
N=5

7. 7
Rosen, section 4.2, question 4
Abowlcontains10redand10yellow
balls
b)Howmanyballsmustbeselectedto
ensure3yellowballs?
Considerthe“worst”case
Consider10redballsand2yellowballs
Youcan’ttakeanotherballwithouthitting3
yellowballs
Thus,theansweris13

8. 8
Rosen, section 4.2, question 32
6computersonanetworkareconnectedtoatleast1
othercomputer
Showthereareatleasttwocomputersthatarehave
thesamenumberofconnections
Thenumberofboxes,k,isthenumberofcomputer
connections
Thiscanbe1,2,3,4,or5
Thenumberofpigeons,N,isthenumberofcomputers
That’s6
Bythegeneralizedpigeonholeprinciple,atleastone
boxmusthaveN/kobjects
6/5=2
Inotherwords,atleasttwocomputersmusthavethesame
numberofconnections

9. 9
Rosen, section 4.2, question 10
Consider5distinctpoints(x
i,y
i)withintegervalues,wherei=1,
2,3,4,5
Showthatthemidpointofatleastonepairofthesefivepoints
alsohasintegercoordinates
Thus,wearelookingforthemidpointofasegmentfrom(a,b)to
(c,d)
 Themidpointis((a+c)/2,(b+d)/2)
Notethatthemidpointwillbeintegersifaandchavethesame
parity:areeitherbothevenorbothodd
 Sameforbandd
Therearefourparitypossibilities
 (even,even),(even,odd),(odd,even),(odd,odd)
Sincewehave5points,bythepigeonholeprinciple,theremust
betwopointsthathavethesameparitypossibility
 Thus,themidpointofthosetwopointswillhaveintegercoordinates

10. 10
More elegant applications
Notgoingover…

11. 11
Quick survey
I felt I understood the material in this slide set…
a)Very well
b)With some review, I’ll be good
c)Not really
d)Not at all

12. 12
Quick survey
The pace of the lecture for this slide set was…
a)Fast
b)About right
c)A little slow
d)Too slow

13. 13
Quick survey
How interesting was the material in this slide
set? Be honest!
a)Wow! That was SOOOOOO cool!
b)Somewhat interesting
c)Rather borting
d)Zzzzzzzzzzz

14. 14
Today’s demotivators