Together we will work through countless problems and see how the pigeonhole principle is such a simple but powerful tool in our study of combinatorics. Last but not least I found a 12 page pdf file on the pigeon hole principle which is worth a read.Consequently, using the extended pigeonhole principle, the minimum number of students in the class so that at least six students receive the same letter grade is 26. Chai Wah Wu has made some notes on the Generalized pigeonhole principle where he states several other statements which are a consequence of the pigeon hole principle. Other places I have seen the pigeon hole principle used is especially in computer science where two applications has been to prove that hash tables will have collisions and that loss less compression doesn’t work on all files.ĭijkstra wrote a short note on the underserved status of the pigeon hole which was pretty insightful. Unlike many of the other proof techniques we have dabbled in earlier. This proof is a good illustration that the argument can be used to prove existence of a certain property, but given a set specific set A the proof does not help us with actually finding the equal sums. This is larger than 1001 and thus there must exists two sums which are the same. We have that for each of the 10 numbers, so that means we have 2 10=1024 options to make a sum of the elements of A. We haven’t found the two sums, but we have proven that they exist.Ī number can be present in the sum or not, which means we have 2 options. So if we can show that the number of sums we can make from the 10 numbers is larger than 1001 we have proven that there are two equal sums. Proof: The number of “holes” is the possibilities to make a sum of the 10 numbers is 1001 since we can go from 0 to 10*100=1000. Then it will be possible to make two different sums of elements from A which are the same. Proposition: Choose a set A of 10 random integers between 0 and 100. So if there are N people and N-1 possibilities to the number of people each person can shake hands with then at least 2 people have shook hands with an equal amount of people So we are down to N-1 possibilities of people each person can shake hands with. So 0 and N-1 possibilities are mutual exclusive. If one person has shaken hands with everyone else, then there is no one who hasn’t shook hands with no one. Proof: A person can shake hands with between 0 and N-1 people since you cannot shake hands with your self. Proposition: At least two people have shaken hands with the same number of people. (mathematics) The theorem which states that any partition of a finite set of. So there is no distinguishing who took the initiative to the greeting. pigeonhole principle (countable and uncountable, plural pigeonhole principles). If two persons shake hands then it counts as both of them have shaken hand with one person. There are N people at a party some of them have been shaking hands, and some haven’t. I will show one of my favourite examples of it which I do not find intuitive at first glance. So an example if you have 10 balls which are to be put into 9 boxes then at least 1 of the boxes contains at least 2 balls (unless you drop one of them…). My first comment on that was “well duh!”, that is obvious, but it can actually be used to prove some less intuitive things. The pigeon hole principle is a counting argument stating something as simple as “if you have n items which are to be put into m < n boxes then there is at least 2 items in one of the boxes”.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |