MT2504 Combinatorics and Probability: Chapter 2

Counting combinatorial structures

Chapter 2

Theorem u ') .
PIGEONHOLE PRINCIPLE

let m n r EIN se m > nr
, ,




If m objects are divided into n sets
,
at least one set contains at least rtl
objects .




r =L In ) ( ie number of times can
.



you

wholly fit n into m ]

Proof :




Let It be a set with III -
- m




Let Ai ,
. . .


,
An E II sit # =
it ,
Ai e- Doesn't have to be a
partition
then
,


IA I ,
t -
- -
t IA n
I > m > nr




Impossible if til Ail Er
( then El Ail Snr
)

Remarks :




"



pigeonholes
"
tf then hole has 3 Rtl
put into
pigeons
•
n
m
pigeons are one


Proof used
•
a more basic fact :




Ha , .
.
- .
.
an EIR
,
mix ai
s
,
ta la ,
t - -
-

tan )

' 2
Eg
'




Show that
among
6
people (A ,
O C
, , QE F) ,
,
there are either 3 who all know each other
,
or 3 who are


mutual strangers .




Pick one
person arbitrarily (A) .
There are 5 other people ( 8,40 E
,
F) who know
I don't know this person .


,


Divide 5 into
remaining people two sets :




•
One set contains all who know A
•
The other set contains all who don't know A .




P H P three
By -
-


,
one set must contain at least
people


A
Suppose → 3 know :




we ( without
losing generality) 8 and all know A then either :
can C 0
say ,
.




of 8 C and 0 know each other ( O, C and 0 mutual strangers )
-

None .

,


32 each other B and C which each other
-




know in A 8 C know
,
say ,
case
, ,




Suppose 73 don't know A :




we can
say
( without
losing generality ) 8, c and 0 don't know A . then either :




B C D all know each other ( found set each other)
of three people who
-




, , know .




-

72 don't know each other 0 and C which mutual
, say ,
in case A. 0
,
c are
strangers

, I -3
Eg
Show that in
any set of m
people ,
at least two have the same number of friends in the set .




Each has between O and m l friends in the set
person
-

.




sets
Let 8; be the subset people with friends Oo Bm ( these
disjoint)
!
i → m
of .
.
. . -

,
-
,
are



of Bo
observation : one or Bm -

i
is
empty .




↳ If somebody friends with
everybody ,
then everyone
has at least one friend ( Oo empty)
↳ If someone knows
nobody then no one knows
everyone ( i.e . Bm -
i
is empty ) .




,




So m
people ,
m -
I subsets
,
PHP says some toil > 2




Cl u)
Eg
-




How many
people do we need to
guarantee 5 of them have
birthdays in the same month ?

(12×4)+1 =
49
n
p
-




Let Ai be the set of
people with birthdays in month i e El
,
. . .
,④}
we want in some
Ai

↳ rt ,




If 12×4=48 S PHP if
people
nr
then by
m
month
>
49
-
s, in some .

,




( 1. s )
Eg
Is there multiple of 1413 in the 7 77 777 7777 ?
a
sequence , , , ,
. .
.




Let ai
= 77 . .
-7 so a
,
-

- 7
,
ai 77
-

i times




set bi
-

-


ai mod 1413 ( remainder after
dividing by 1413 ) for I a- is 1413 .




CASE 1 :




some bi -
- O
.
Done since if O -
ai mod 1413 then 1413 divides ai .




CASE 2 !




No bi -
-
O .
there are 1413 bi 's and only 1412
possibilities for them :




Possibilities 1412 ( remainder 't itself)
:
1,2 , .
-
-


,
can be 1413

there bi bj (i j) ( P H P)
↳ Hence exists #
by
= - .




Assume j > i :




Ioi La
a ai
)
- -




;
-




; -
i


A
-
-
7 7 7 7
; . . -




7 7 7
aj
=
-
. . .




77 70 O
aj a
-
= . . - . - -




,
-
Ioi
Aj -
i




"

By construction :
1413 divides 10 ( aj -
i )
To finish : 2 does not divide 1413 and 5 also does not divide 1413 .
.
'


.
10 does not divide 1413
,


Hence 1413 divides ai which is in the
j sequence
-




,




so ans =

yes
=

, Definition :
the CARTESIAN PRODUCT
' '


Y
"
→ X cross




II ×

Y of sets IT ,
'T is the set


x
'T -

-




{( x
, y ) :
x c-
II , ye 'T }
of all ordered pairs w/ ace # , ye 'T
[ Cx , y
) # Cy ,
x ) ]

Eg :




{ 1.2.33 xea.b.is
-

-




{ !! :} ! !!:b;) ! ! }
NOTATION ( 2 2) -




S E Ix 'T


r. G) =/ { y :( x. g) ES } Cy ( s )
=


{ x :( x. g) es }
r = row c
-
-
Col



G 3)
Eg -




TI -

-




{ a
,
b. c. d } Y -

-

{ 1.2.33
,
,




s=E@④C kiss , ,
( a. 21 ,
3,④D3 EXIT

( s)
r⑤( s ) 2
⑧
=3
-

-