Clearly, f(i) can take values only between 0 and (n − 1). If there are n persons in the group, then let the number of friends the ith person has be f(i), i = 1,…, n. Example 01Īssuming that friendship is mutual, show that in any group of people we can always find two persons with the same number of friends in the group. Let us consider some examples of its application, in detail. in any group of 13 people, at least two are born in the same month.if 8 people are picked in any way from a group, at least 2 of them will have been born on the same weekday.This result appears very trivial but has many applications. So, in whichever way we place these pigeons, at least one hole will have more than one pigeon in it. Under this assignment, each hole has one pigeon, but there are still (m−n) pigeons left. Now, beginning with p 1, we assign one each of these pigeons the holes numbered 1,2, …, n, respectively. Let us label the n pigeonholes 1, 2, …, n, and the m pigeons p 1, p 2, …, p m. Then, under any assignment of objects to the boxes, there will always be a box with more than one object in it. This is actually an application of the pigeonhole principle, which we now state. Wouldn’t you agree that regardless of the way the objects are placed in the two boxes at least one box will have more than one object in it? On the face of it, this seems obvious. Let us start by considering a situation where we have 10 boxes and 11 objects to be placed in them. Its proof is very simple, and amazingly, it has several useful applications. Here we will see how obvious the pigeonhole principle is. Theorem 2 (The Generalized Pigeonhole Principle):.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |