Pigeonhole Principle - Discrete Mathematical Structures Video Lecture - Computer Science Engineering (CSE)

ha ha ha
you
you
in the next few lectures we shall
consider some topics in combinatorics
the first one we shall consider this the
pigeonhole principle it's a very simple
concept and we shall consider the
concept and then some problems and other
things but the simple form of the
pigeonhole principle is like this if n
plus 1 objects are put into n boxes then
at least one box contains two or more of
the objects the very simple thing very
easily understandable so in fact it is
said something like this if n plus 1
pigeons are put into n pigeon holes at
least one pigeon hole will contain two
or more pigeons that is why this concept
is called the pigeonhole principle it's
a very simple idea let us see how this
idea can be used to solve some problems
some of applications are as follows
among 13 people there are two who have
their birthdays in the same month
because there are only 12 months there
are 13 people two of them will have
their birthday in the same month in very
simple concept the next one is given m
integers a1 a2 am there exist K and L
where K and L are between 1 and M such
that a k plus 1 plus a k plus 2 plus a L
is divisible by M the disk if we take
the successive numbers and their sum
that will be divisible by M if you put
it less formally there exists
consecutive yes in the sequence a 1 a 2
a.m. who sum is divisible by M how do
you use pigeonhole principle to prove
this to see this consider the m sums a 1
a 1 plus a 2 a 1 plus a 2 plus a 3
consider a 1 a 1 plus a 2 a 1 plus a 2
plus a 3 and so on there are M such sums
if any of these sums is divisible by M
then obviously the conclusion holds
the result follows so this we may assume
that each of these sums has a nonzero
remainder when divided by M that is none
of these sums are divisible by M and so
when divided by M they will leave some
remainder and that is nonzero so it will
be from 1 to M minus 1 of the integers
from 1 to m and the remainder will be
equal to 1 of the integers 1 2 3 up to M
minus 1 now we have M sums and only M
minus 1 remainder M 1 M minus 1 possible
values for the tremendous two of the
sums will have the same remainder been
divided by n therefore there are two
integers K and L and let us assume that
L is greater than K such that a 1/4 plus
a 2 plus a K leaves the remainder say R
when divided by M and the a 1 plus a 2
plus a 3 after Al also leaves the same
remainder R when divided by M that means
a 1 plus a 2 plus a K is equal to sum'
be in TM + R where B is an integer and a
1 plus a 2 plus a 3 up to Al is cm plus
R Percy is an integer now L is greater
than K so subtract this from this you
will find that a k plus 1 up to L that
is the remaining elements from here
after a K that is equal to C minus B
into y m that is where C is an integer B
is an integer so C minus B is an integer
and this sum a k plus 1 up to L is
divisible by ya
thus we prove that a k plus 1 a k plus 2
up to Al is divisible by ya
this is another simple application there
are strong forms of the pigeonhole
principle let us consider the same idea
but extended in a slightly different way
let Q 1 Q 2 QN be positive integers if Q
1 plus Q 2 plus Q 3 plus Q n minus n
plus 1 objects are put into n boxes then
either the first box contains at least
q1 objects or the second box contains at
least q2 objects and so on are the nth
the box contains at least qn of there's
this again very simple let us see there
are n boxes 1 2 3 N and there are Q 1
plus Q 2 plus Q n minus n plus 1 objects
suppose the first box contains less than
Q objects maximum it can handle this Q
minus 1 and if it contains less than Q 2
objects the maximum it can contain is Q
2 minus 1 and proceeding like this
the maximum number this can have is Q n
minus 1 if the nth the box contains less
than Q n minus 1 elements so the total
number of elements you can have in all
the boxes will be Q 1 plus Q 2 plus Q n
minus n in this case so if you have Q 1
plus Q 2 plus Q n minus n plus 1 objects
at least one of the boxes will contain
more than they're supposed to element
that is either the first box will
contain Q and objects are more our
second box will contain Q two objects
are more or the third box will contains
Q three or more objects harder in the
box will contain Q are not more objects
putting it in another way making use of
suppose Q 1 is equal to Q 2 is equal to
Q 3 etcetera suppose n into R minus 1
plus 1 objects are put into n boxes
then at least one of the boxes contains
our art more outlets if each box
contains less than our object the
maximum it can contain is our minus 1 so
the total een in boxes we can have only
n into R minus 1 objects but now there
are n into R minus 1 plus 1 objects so
at least one of the boxes will contain
our our more objects putting it in
another way this is another form of the
statement if n integers m1 m2 MN have an
average m1 + m2 plus MN by M because if
you have an integer the average is given
by this number and if the average is
greater than R minus 1 then at least one
of the integers m1 plus m2 MN is greater
than or equal to R because otherwise the
average will not be greater than or
minus 1 so these are different ways of
putting the pigeonhole principle
depending upon the application we take
the proper form the idea is very simple
but when we use it to solve problems we
have to think and apply it in a proper
manner let us consider some problems
a man hiked 10 hours and covered a total
distance of 45 miles it is known that he
hiked 6 miles in the first hour and only
3 miles in the last hour show that he
must have hiked at least 9 miles within
a certain period of two consecutive of
us so this is the problem a man hiked
for 10 hours so let a 1 a 2 a 10 be the
number of miles he hiked in the I tower
so AI is the number of miles
he hiked in the high tower kosai will
vary from 1 to now we know that a 1 is 6
and a tennis and it is said that we have
to prove that consecutive two hours he
would have hiked at least nine miles
suppose not suppose he has not typed
nine nine miles or more in any two
consecutive hours
then what does that mean a 1 plus a 2
will less than 9 K 2 plus a 3 is less
than 9 and so on a 9 plus a 9 plus a 10
just less than so adding you will get a
1 plus 2 times a 2 up to a 9 Plus 8 n is
less than 9 times 9 81 add one more a 1
and a 10 but we know that a 1 and a 10
or 6 and 3 respectively so that is
equivalent to adding 9 you get that 2
times Sigma AI is less than 90 Sigma AI
which would mean it is contradicting the
fact that he has hiked 45 miles in 10
hours
so but we know that the man hiked for 10
hours and covered a total distance of 40
minutes so if you assume that he has not
hiked 9 miles or more than any two
consecutive hours we come to the
conclusion that the total distance
covered by him is less than 45 which is
not true so we are arriving at a
contradiction and that would mean that
he has right he has height 9 miles or
more in some consecutive hours at least
in some consecutive
let us take some more examples the
circumference of a roulette wheel is
divided into 36 sectors to which the
numbers 1 to 36 are assigned in some
arbitrary manner show that there are
three consecutive sectors such that the
sum of their assigned numbers is at
least 56 again this problem is very
similar to this one you have a
circumference sub cell which is divided
into 36 possible s a 1 a 2 a 3 and so on
a 36 and each of them is assigned a
number between 1 to 36 and the problem
says that we have to show that placed in
one place 3 consecutive sectors the sum
will add up to 56 are more suppose not
in the same idea if you a 1 a 2 a 3 are
the same
suppose the conclusion is not true then
you have a 1 plus a 2 plus a 3 is less
than or equal to 55 if it is not 56 or
more it has to be less than or equal to
50
similarly a 2 plus a 3 plus a 4 is less
than or equal to 55 and proceeding like
that a 35 plus a 36 plus a 1 is less
than or equal to 55 a 36 plus a 1 plus a
2 is less than or equal to 4 different
now I add up this you will get a 1 is
occurring in 3 places a 2 is occurring
in 3 places so the sum will be Sigma 3 3
times Sigma a that will be less than or
equal to 55 into 36 this is there are 36
inequalities adding the right hand side
of the equal
did you get this but what is Sigma ETA
is between one and 36 the numbers one
and between the numbers between 1 and 36
are assigned to a 1 a 2 a 3 so this will
be 3 into Sigma a will be 36 into 37 by
to discuss the sum of the first n
integers is given by n into n plus 1 by
2
here the sum of the first 36 integers is
given by 36 into 37 by 2 that is less
than or equal to 55 into 36 canceling 36
on both sides you'll get 3 into 37 is
111 111 is less than or equal to taking
the 2 on the other side you get so you
get the result harder than 11 is less
than or equal 210 which is not correct
so you are arriving at a Carnot
contradiction so the result follows that
is there are three consecutive sectors
such that the sum of their assigned
numbers is at least 56 I can see the
similarity between this problem and the
previous problem the third one is and
you can also see the application of the
pigeonhole principle
the third one is like this from the
integers 1 200 1 to 200 100 and one of
them are chosen arbitrarily show that
among the chosen numbers there exists
two such that one divides another so the
numbers are between 1 and 200 1 2 to 200
and you are selecting hundred and one of
them
show that there are at least two where
one will divide the other now this can
be solved in this manner you have
hundred holes or hundred holes or boxes
one for each one for the odd numbers 1 3
5 7 like that there are 100 boxes take a
number if you pick a number I express is
some R into 2 power each number you can
express like this R into 2 power K where
K will be greater than or equal to 0 for
example if I take 55 that is 55 in to 2
power 0 and directly if I take say 112
112 is how many times 64 8 divided by 8
7 into 2 power isn't it 16 into 700 and
we can write like this now whenever you
have a number like this you write it as
R into 2 power K so put this number in
the Box corresponding to R so if I if I
have selected 55 I will put 55 in the
Box corresponding to if you had selected
had rental I will put it in the Box
corresponding to 7 so when they sell it
101 numbers out of 200 numbers and put
them in the boxes corresponding to these
like this by the pigeonhole principle
one box will contain at least two two
elements suppose a particular box X
contains two elements then there are two
numbers M is equal to X into 2 power P
this box corresponding to X X is an odd
number
it contains two elements same manner
then Y can be represented as X into 2
power P n will be represented as X into
2 power now obviously P will be less
than Q or one of them will be less than
the other P and Q cannot be equal
because MN is not different
suppose M is greater than M then P will
be greater than Q and M is divided by N
and M by n will be equal to 2 power 3
minus so M is divided by n there are two
numbers such that one divides the other
so we prove that result so you can see
how the pigeonhole principle is applied
here the next is select is a
continuation of the Select hundred
integers from the integers 1 to 200 such
that no one of them is divisible by any
other so from 1 to 200 you are asked to
select 100 of them so that no two of
them are such that one device other if
you select 100 and 102 to 200 you will
realize that none of them divides other
the you can see like this argue out like
this even if you take the least element
and the smallest multiple multiplied by
the smallest integer it will be 200 and
2 which exceeds this so this will not
divide any of this
and similarly any one of them will not
divide other that is one argument and
when we considered the earlier thing try
to express each one of them as X into 2
power some cake and try to put in one
each one in one of the pigeonholes
1 3 5 7 etc this hundred pigeonholes you
will realize that these hundred numbers
will be put
in 100 different boxes each one will
contain only one of them you can try
that and check whether it is correct no
two of them will be put in the same box
so you can take it as an exercise and
try putting these numbers into those
hundred boxes the next problem is also a
somewhat similar one show that given any
52 integers there exist two of them who
some are else whose difference is
divisible by the numbers can range in
any way so let a 1 a 2 a 50 to be the
integers there are some integers and you
are asked to show that there are two of
them such that the sum will be divisible
by 2 or the difference will be divisible
by 2 you can always select 2 from these
52 integers such that the sum are the
difference of will be divisible by 100
how do you prove that now any number a I
you can express as hundreds K plus bi a
we can express a number like this
a is equal to 100 K plus B what is the
range for BA it will be from 0 to 9
now let us consider some boxes like this
corresponding to 0 1 2 49 you consider
51 boxes like this if then a be any
number a a is of the form handed K plus
bi now if bi is 0 you put it here if ba
is 50 you put it here if ba is equal to
1 or 99 you put it here in the Box
corresponding to 1 so you put ba in in
the Box J yes bi bi is equal to J or
hundred minus
now how many boxes are there there are
51 boxes there and how many numbers are
there there are 52 numbers so by the
pigeonhole principle two of them will be
put in the same box
so two numbers say am and am will be in
the same box because of the pigeonhole
principle suppose I am is equal to some
100 100 times k plus BM and a n is
hundred times L plus BM they are in the
same box and let the Box be the gate box
box D so BM is de are hundred minus e BN
this also they are undermining suppose
BM is the same as B n then JM minus a n
will be 100 times K minus L so the
difference is divisible by hand suppose
VM is a and B and is 100 minus D suppose
BM is day and be honest hundred minus
then a.m. plus a and will be handed into
k plus L plus BM plus BN will be hundred
so the sum a.m. plus a n will be
divisible by 100 so any number yeah
you're a expresses 100 k plus bi bi
where ba will be from 0 to 99 and you
consider 51 boxes like this 0 1 2
corresponding to 50 and you put a number
in a corresponding box J if ba is JR 100
minus T for example if ba is 1 you will
put here if ba is 99 also you will put
here VI is 2 you put here ba is 98 also
you put it here like that you put
because there are 52 numbers and 51
boxes at least one of them will contain
two numbers by the pigeonhole principle
and suppose I am and then M are in the
same box day then a.m. you can write in
the form 100 k plus BM and the a and you
can write as 100 l plus BN where BM will
be j are hundred minus J and B and also
will be J are hundred minus T if they
are the same
consider the difference the difference
will be divisible by hundred if one is
de and nano that is 100 minus de
consider the sum of the two numbers the
sum will be divisible by hundred so this
way we can prove that given any 52
integers there exist two of them who
some are else owes difference is
divisible by hundred take another
problem let us go through the statement
of the problem carefully
a student has 37 days to prepare for an
examination from past experience she
knows that she will require no more than
60 hours of study
she also wishes to study at least one
hour per day show that no matter how she
she jewels her study time a whole number
of hours per day however there is a
succession succession of days during
which she will have studied exactly 13
hours a student has 37 days to prepare
for an exam and she needs to prepare for
60 hours a student has 37 days to
prepare for an examination from the past
experience she knows that she will
require no more than 60 hours of setting
she also wishes to study at least one
hour per day
show that no matter how she schedules
her study time there is a succession of
days during which she will have study
the exactly 30 13 hours suppose on the
first day she studies is she has studied
for a year one at the end of the second
day she has studied for a two of us at
the end of the third day she has studied
for a three hours that is the first day
she studies for ei one of us thus again
the day first hence again they put
together she studies for she has studied
for eight two of us and the third day
that is the first three days she has
studied a three hours and so on so on
the 37th day she has studied for 60
hours so this is an increasing sequence
so every day she yay
is the number of hours
studied up to ice today so this
particular sequence is an increasing
sequence because every day she studies
at least one hour and
these numbers are between one and sixty
because maximum she stood is only for 60
hours and considered this sequence now
what we want to prove is in consecutive
some consecutive days yes exactly
studied that in our studies
some say a J minus AI is equal to where
J is greater than I can this is what we
want
now consider this sequence a 1 plus 13 a
2 plus 13 etc a 37 plus a 1 a 2 a 3 a n
is an increasing sequence so we are
adding 13 to every number so a 1 plus 13
a 2 plus 13 a 3 plus 13 is 37 plus 13
there is also an increase in sequence
and all numbers are all different so
this is an increasing sequence and the
values will range from 13 to 73 a 37 is
60 so 60 plus 1373 values will range
between these two 13 and 73 so now
consider the numbers a 1 a 2 a 37 a 1
plus 13 etcetera up to a 37 plus 13 how
many numbers are there here 37 plus 37
74 numbers are there
and the value is a a ranges from 1 to 60
the other sequence the numbers range
from 13 to 73 so these numbers the value
ranges between 1 to 73 these numbers are
between 1 to 73 and there are 74 such
numbers so two of them will be equal
obviously by the Prince of pigeonhole
principle two of them will be equal now
you know that none of these numbers are
equal because every day she studies at
least one hour these numbers are all
different and these numbers are all
again different because with each number
you are riding 13 so the fact that two
of these are equal would mean that some
AJ will be equal to some AI plus 30 okay
obviously gay has to be greater than 9
so AJ minus AI will be that is from the
I plus 1 today till the day today she
has exactly studied for 13 hours that is
from the I plus once a day to day today
she has studied for 13 hours so you can
see how the pigeonhole principle is
applied here
let us take one more problem
suppose that in a group of six persons
each pair are either friends or enemies
prove that among six either there are
three persons who are mutual friends
each is a friend of the other or else
there are three persons who are neutral
enemies each is an enemy of the others
also show that this is not true for five
persons so you can consider it like this
you are having six persons a b c d you
if a and B are friends I will put a line
like this straight line if a and B are
enemies I will put a line like this so
if you have
x and y are friends you consider like
this if x and x and y are enemies
consider
a-and consider three of his friends see
there are five people and either he will
have three friends are three enemies
right if if a has three friends you can
proceed following men either among the
five their possibilities are a has there
are a part for me there are five people
the possibility is is five friends
friends and enemies five friends no
enemies four friends one enemy three
friends to enemies two friends three
enemies one friend for enemies zero
friend all enemies so either a will have
three friends are he will have three
enemies either this is my region whole
transmen either a will have 3 prints of
three
suppose he has got three friends we'll
see how we can deal with the case when
he has three enemies it's similar
suppose he has three friends say suppose
B C and D are his friends then consider
B and C F C and D and B and E if either
B and C are friends then you have three
friends do you three mutual friends or
if G and C are friends again you are
having three friends mutual friends if
otherwise if B and E are friends again
you are having three mutual friends on
the other hand none of them are little
friends suppose B and C are enemies
suppose C and G are also enemies and B
and we are also in this then we are
having three mutual enemies so in this
case you are having three mutual enemies
so either you are having three friends
are three mutual enemies the other way
round
supposing a has three enemies and two
three are more enemies a has three
enemies now consider again B and C if
they are enemies you are having three
mutual enemies if C and D are enemies
like this you are having three mutual
enemies if B and D are enemies then
again you are having three mutual
enemies
otherwise if they are not enemies B and
C will be friends C and E will be
friends and B and G will be different so
you are having three mutual friends so
this shows that if either you have three
mutual friends are three mutual enemies
now the same is not true for five
persons a b c d the reason is if you
have apart from here have five persons
then either three of them will be
friends to a are three of them will be
enemies more than three will be friends
or more than three will be three or more
will be enemies this is because you can
put like this now apart from you there
are only four of them so two can be
friends and two can be enemies so the
fact that three of them a will have
three friends are three enemies does not
hold anymore
so suppose B is friend to a and he is
friend to a and C is enemy to a and D is
also enemy to yeah I can design in such
a way that you do there are no three
people who are friends are there are no
three people who are enemies now yeh and
ye are friends a and B are friends
so suppose it is possible that B and D
are enemies and a and D are enemies a
and C are enemies but C and D can be
friend it can happen like that let us
draw the other arcs also now in this
case you have to draw this arc
one two three four five six arcs we have
run for more rocks we have to draw
suppose B and C are friends all right
then D and C are friends B and C are
friends it is possible that B and D are
enemies you can have like this
and E and B are enemies B and D are
enemies so it is possible that D and E
are friends right
so in that case you do not have three
enemies or three friends and similarly
you are having D and C as friends and D
and E as friends so it is possible that
C and D are enemies now if you take any
three of these vertices you will find
that no three of them are friends are no
three of them are mutual enemies so it
is possible to draw a graph like this
with two different types of ox such that
five of them are of one one type and
five of them of around the type and you
have the condition that no three of them
are mutual friends are no three of them
are mutual enemies it is possible to
draw like this the reason is when they
say yeah apart from me there are five
people of which you put friends and
enemies in two boxes friends and enemies
five people you try to put them one of
them should have contain three and three
or more
absolutely yeah will have either three
friends are either it will have three he
will have three enemies and in that case
we argued out how there are how you get
three mutual friends are two mutual
enemies now apart from you if you are
only four people that condition does not
hold if you have two boxes friends and
enemies you can put two two in each of
them and then there you can construct a
graph like this which shows that there
are none you don't have three mutual
friends or mutual so the pigeonhole
principle is again used here
let us consider one more problem again
similarly same idea a very simple idea
but
you have two concentric discs the
circumference of the to concentrate
disks are divided into two hundred
sections each as shown in the figure let
us see the figure you have two
concentric sized circles like this and
the circumference is divided into two
hundred sectors like this for the outer
disk hundred of the sections are painted
red and hundred of the sections are
painted blue for the inner disk the
sections are painted red are blue in an
arbitrary manner show that it is
possible to align the two disks so that
100 or more of the sessions sections are
the inner disks have their colors
matched with the corresponding sections
on the outer disk the figure is like
this now in one position you are having
a disk like this suppose one to 200 and
similarly here also one to 200
how many ways you can all align them
first is 1 and 1 can be aligned in a
manner then you can rotate and two can
come aligned with one then you can again
rotate and three can come in alignment
with one so that two will come with 200
and 199 one will come like this I am
rotating the anti-clockwise direction so
you can rotate in such a way that you
get the next alignment the first
alignment of course one and one if I
number them as 1 to 200 and 1 to 200
Milana to 200 and 200 aniline and so on
if I rotate through one sector then two
will align with one and so on so how
many possible alignments can you have
you can have possibly 200 alignment and
the problem is it is possible to align
the two discs so that hundred or more of
the sections of the inner disk have
their colors match with the
corresponding sections on the outer disk
now in the outer disk hundred of them
are colored blue and hundred are painted
red and in the disk they are arbitrarily
painted red dark blue so take in one
alignment in one alignment suppose this
particular disk is colored red out of
the two hundred possible alignments in
hundred possible alignments it will
match with the corresponding sector in
the outer disk
so in the 200 alignments the first
sector will match in hundred of the 200
element second sector will also match in
hundred of the alignments third sector
will also have matched in hundred of
elements and so on so totally the number
of matches will be two hundred in two
hundred twenty thousand matches we found
the matches
see in one alignment will count the
Matis in the second element to count the
Matis the third arrangement you found
the matches like that in the 200
elements to count the matches the total
number of matches will be 20,000 the
reason is each sector in the inner
circle is painted red dark blue and
outer sector 100 of them are painted red
and hundred of them are painted blue so
if you take this sector which is painted
red in hundred of elements it will match
if you take the next sector it will be
blue or it so in 100 of them it will be
matching and so on so if you count the
number of matches in all the elements it
will add up to 20,000 and how many
alignments up there there are 200
islands so the average is 100 and if you
look at the so the average is 100 so at
least in one alignment hundred or more
of the sector's will match the
corresponding colors here we are you
making use of this if n integers m1 m2
MN have an average which is greater than
R minus 1 then at least one of the
integers M 1 plus M 1 M 2 M n is greater
than or equal to R so if the number
there are 200 elements let us call them
at alignment one alignment to alignment
200 the number of matches you call it as
M 1 M 2 and M 200 the sum is my M is
20000
so the average Sigma mi by two hundred
hundred so it is greater than 99 so here
in this example m1 m2 MN represent the
number of matches in each alignment and
the average is greater than R minus 1
that is 99 it is at least hundred so at
least one of them should be R the number
of matches in at least one of them m1 m2
MN em 200 is hundred so we are making
use of this form of the pigeonhole
principle here so let us recall the
pigeonhole principle and the different
versions again and it can be used to
solve problems like this the idea is
very simple but each problem in your
tackle you have to think in a different
manner for the solution the simple form
is this n plus 1 objects are put into n
boxes then at least one box contains two
or more of the objects the stronger
forms are like this let Q 1 Q 2 Q and B
positive integers then if Q 1 plus Q 2
plus Q n minus n plus 1 objects are put
into n boxes then either the first box
contains at least you one or the second
box contains at least Q 2 and are the
nth box contains at least queuing
objects the other two forms are like
this if n into R minus 1 class objects
are put into n boxes then at least one
of the boxes contains R are more of the
objects and if you take that another
form is if you take the average of n
elements if it is greater than R minus 1
then at least one will be greater than
or equal to