![]() Show that some pair of persons must have attended the function at least twice.ĥ persons can be paired in C(5, 2) =10 ways. On 11 occasions a pair of persons from a group of 5 was called for a function. Thus, if 10 points are chosen, at least two of them must lie in one of the 9 triangles. If 10 points are chosen in an equilateral triangle of side 3 cm, show that we can find two points at a distance of at most 1 cm.īy drawing lines parallel to the sides and through the points trisecting each side, we can divide the equilateral triangle into 9 equilateral triangles of side 1 cm. But, by dropping the common elements in them, we are left with disjoint subsets with the same sum. Now, note that two subsets that we get with the same sum, may not be disjoint. So, some pigeonhole will have more than one subset with the same sum. The 1024 subsets have to be put in 1016 pigeonholes. Put a subset in the pigeonhole marked with the sum of the numbers in the set. The set of 10 positive integers have 2 10 = 1024 subsets. So, consider pigeonholes marked 0, 1, 2,…, 1015. The highest numbers we could be given would be 97, 98, …, 106, which add up to 1015. Given any ten different positive integers less than 107, show that there will be two disjoint subsets with the same sum. Clearly, the distance between these two points is at most ½ meter. By the pigeonhole principle, at least one of these smaller triangles will have two points in or on it. These four triangles may now be considered as boxes and the five points as objects. Show that we can find two points at a distance of at most ½ meter.ĭivide the triangle into four equilateral triangles of side ½ m by joining the midpoints of the sides by three line segments (see Fig). Suppose 5 points are chosen at random within or on the boundary of an equilateral triangle of side 1 meter. Then the corresponding i’s have the same number of friends in the group. ![]() Therefore, by the pigeonhole principle, two f(i)’s must be equal. So, then f(i)’s can take only (n − 1) distinct values. So, only one of the values 0 or (n − 1) can be present among the f(i)’s. In this case, no person can be friends with all the other (n − 1) people. If some f(i) is 0, it means that the ith person does not have any friends in the group. 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. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |