today we'll talk about the pigeon hole principle this is huge this is a very very important thing like I said before a lot of proofs are done bya contradiction as a proof technique this is a very nice method of proof that is used to solve some very very important things so let's talk about it what is the pigeon hole principle uh on the left here I have a bunch of pigeons we can also call them items and on the right we have pigeon holes which we can also call containers pigeon holes are just places where pigeons go and the answer and the question is when we distribute these pigeons into the pigeon holes what do we see what is something that we always see okay let's let's do this let's put this one in here let's put this one in here let's put this one in the first one and this one down here so then we have a three 0 one distribution that's nice so now I say well okay actually I want to distribute all these pigeons but only have one in each box so we say okay let's put this one in here this one in here this one in here oh crap what do I do with this extra one well let's break the rules and just put it in this one box up here so we have a 211 distribution here and the pigeon hole principle states that if you have more pigeons than pigeon holes there's always going to be be one pigeon hole with more than one pigeon in it and I think that's something that's pretty obvious but we generalize it a little bit more than that and we say that if we have M items and we have n containers if it's the case that the number of items is greater than the number of containers there is at least one container with the ceiling of M over n items and I should mentioned that the ceiling of m/n what it does is if you have a number X Point say Su values y z w so on and so forth what it does is it outputs x + 1 so it just rounds the number up so previously we saw we had four items in three containers this is equal to 1.3333 so on and so forth but then the ceiling function rounds it up to two so there's at least one container with two pigeons in it what if we had 10 items in four containers well that means there's at least one container with three items in it of course there can be more we can distribute it so all 10 items are in one container but what we're saying is that we'll never get a distribution that has less than three items in any container or less than you'll never have a distribution where there are less than three items in all of the containers it's not going to happen so here's a question what do we do with it we have this really cool sort of intuitive knowledge of this pigeon hole principle what can we prove with it well here's an interesting application if you have a group of n people and they may be Str they may be friends they may know everybody they may be unsociable maybe one of them's a serial killer and doesn't really like anybody uh there's always going to be two people who have an identical number of friends within the group that's pretty cool okay so to give a nice example I'm going to pick four people here and we're going to label them just as 1 2 3 and four I'm going to put arrows to represent the friendships here okay well one is going to be friends with two one is going to be friends with four three is going to be friends with four and okay it's kind of nice uh what we see here is that we sort of take the degree of the amount of lines we have going out so we say okay well one has two friends mainly two and four two has the friend one and one only four has friends three and one so this will be two and three has one friend okay so we did a quick little example just to show how this works and let's abstract it a little bit more so we know there are n people okay these are the items now how many friends can each person possibly have and the answer is that each person can have between one and N minus one friends okay so for instance if you're this person here then if you're friends with everybody you're going to have exactly n minus one friends okay so how many elements is n minus one well when you take the pigal principle you take each of these numbers is sort of like a container where you assign a value to each of the end people and it's in one of these containers either they have one friend or two friends or three friends all the way up to n - one friends so what you see is you have n people that can take in N minus one different containers and by the pigeon hole principle this means that there are at least two people that have the same amount of friends or there are at least two values that are going to be in the same container because if you distribute let's let's distribute n minus one people so let's say person one has one friend person two has two friends all the way up to person n minus one which has n minus one friends well then we have this person here n this last person and he has to have either one friend or two friends or 3 4 5 6 all the way up to n minus one friends he can't have less than that he can't have more than that we assume that everybody has at least one friend we are not considering the case where you can have zero friends okay if anyone was thinking oh what about zero friends well no everybody has a friend here and we have a proof that at least two people have the same amount of friends so that's kind of cool it's a little application we can do that sort of is a real world problem for instance here's another cool little example if you have a group of 366 people at least two of them have have the same birthday and this is sort of intuitive but here's the thing it's always going to be greater than or equal to two so you may have it that your group has 365 people with the same birthday that still holds what we're saying is that at least two people will have the same birthday always and I think that's that's kind of a cool thing that we can abstract sort of mathematically and say okay well here's a nice principle for it it's kind of intuitive but there's a nice principle here's an application that is not always so obvious let s equal the numbers 1 through 20 and we're going to say if we pick 11 numbers we're guaranteed that the sum of two picked numbers is 21 this is a little bit you know well how do I prove this how do I make containers like what are the containers that we set up so we have one we have the numbers one 2 3 4 5 all the way up to the number 20 okay well why don't we pair up all the combinations or all the sets that make the number 21 when we add them together so we have 1 and 20 we have 2 and 19 we have 3 and 18 we have 4 and 17 of course remember these are sets so these are not ordered sets okay 6 and 14 wait I'm going to 21 so that should be 5 and 16 6 and 15 7 and 14 I'm going to write them all out just for uh illustrative purposes 9 and 12 and then we finally have 10 and 11 so all of the elements I've listed here are part of the set I have not forgotten any elements and these are all the possible combinations that make up the number 21 we're going to pick 11 numbers and we're going to prove that one of them has a pair that equals 21 so let's pick our numbers very specifically so I want to disprove this so I'm going to pick one in the first set 2 3 4 5 5 6 7 8 9 and 10 so I have a set of 10 numbers where if you add up two of them none of them equal 21 but I said I have to pick 11 numbers which means that this 11th number has to come from one of these sets but if I pick an 11th number from any of these sets then I'm going to have a pair of numbers that equal 21 if I pick 19 I'm going to have 2 and 19 and that'll make 21 if I pick 12 I'll have 9 and 12 which makes 21 so we've proven that if we pick 11 numbers then uh we're going to get the pair that adds up to 21 it has to happen if we pick 12 numbers the same thing will happen if we pick 17 numbers the same thing will happen and what we've done here is we've said Okay what is well it's a little bit more abstract since you're saying well wait isn't this just the floor of 11 over 20 and that would be wrong because what we actually have here is we're picking 11 numbers out of 10 containers or 10 pigeon holes which we see here is equal to two and that's a little bit more confusing at first since you're saying hey well wait there's 20 numbers well you have to put them into s first and that is the one application that maybe isn't so obvious in fact what you can do further with these questions is say well we have some prime divisors of certain numbers we have multiples of certain numbers and you can prove some pretty crazy things with this stuff if you have any specific questions you want me to prove with the pigeon hle principle you can leave them in the comments below what I really like as far as questions are when you have say a grid let's say we have nice a square grid so this is going to be something that looks like this we're going to assume they're all equal distances apart and I say okay well let's give them all lengths of I don't know let's say each of these are going to be 2 cm so you have something like this and I say okay given 17 dots there are always going to be or there is going to exist two dots within uh the square root of 8 cm so that's kind of cool that's actually a pretty uh a pretty crazy proof when you think about it given an 8 by8 square no matter where you put the dots there's always going to be two dots within fruit eight of a cenm together and that's kind of cool in fact I was nice and I said okay here's a grid and I gave you 16 little squares and when I say 17 dots well it's kind of obvious that at least one of these squares has to have two dots but why would I do that why would I give you that information why don't I just say okay here's an 8 cenm by 8 cm box uh prove that with 17 dots you're always going to get a pair of dots that are less than the root 8 cm apart it's pretty crazy right it's kind of a little bit more difficult when I say okay there's an 8 cm by 8 cm square it's a little bit more challenging there in fact what if what if I even took this out and I said okay I want two dots less than otk 8 cm here's the question what is the minimum number of dots that are required to do this and that's even crazier because now I'm saying okay let's let's reverse engineer the problem don't just prove that a certain number of dots is required to be this distance I'm saying okay I want two dots that are within this range no matter where you put them how many dots do I need to do that it's yeah it's a little bit crazy it's a little bit crazy when you think about it but what you have to do really is in this question you have to say okay well I know the diagonal distances are the furthest possible which is root 8 and what this means is that it's going to be really the root of 2^ 2 + 2^ 2 so clearly must have a 2x2 here so we fill this up with a bunch more 2x two boxes okay so these are all 2x two boxes we see there's 16 boxes so what I want is I want the ceiling of n/ 16 to equal 2 and I want the smallest n to do that therefore n has to be 17 now clearly this is a little bit easier to do because I've shown you the original problem then reverse engineered a problem and showed you how to get the answer of the original question question which is a very convoluted way in English of saying uh I basically gave you the answer before and it's really easy to reverse engineer but similar problems like this you'll probably see on exams and they're really good problems because they require you to think about the pigeon hole principle in ways that you probably never thought of it before so that was the PHP really important stuff for proofs I didn't include it in the proof section because because I think it's good to give your brain a little bit of a rest this normally comes at the end of the course comes with counting comes with some other stuff and it's nice to be reminded after not doing proofs for a while of you know a little bit of practice then you learn something new and you know this is nice uh next time we're going to start doing division number Theory that's going to be a lot of fun not really sort of eh some people like it some people hate it Elementary number theory is a very very fun course and it'll go into a lot more depth than we do here so if you enjoyed I suggest teing checking it out but uh that was the pigeon principle that is for sure the end of proof techniques in discret math one