10.5. Pigeon-Hole Principle

So now let us see another interesting counting rule which we encounter very often in discrete mathematics and this is called pigeon-hole principle. So what is the scenario here? So in this example you have 13 pigeons and you have 12 holes and suppose the pigeons are going to randomly occupy these 12 holes. We don't know in what order they will be going and occupying these holes. But irrespective of the way they are going to occupy these 12 holes we can say that there will always exist at least 1 hole which will have 2 or more pigeons.

The Pigeon-Hole Principle states that if you have more items (pigeons) than containers (holes), then at least one container must hold more than one item. In the example, since there are 13 pigeons and only 12 holes, it's impossible to place each pigeon in a different hole, ensuring that at least one hole must contain at least two pigeons. This conclusion follows logically since if each of the 12 holes had just one pigeon, there would only be 12 pigeons, which leads to a direct contradiction of having 13 pigeons.

Imagine you have 13 different colored balls and only 12 boxes to store them. When you try to place each ball in a separate box, you'll find that one box must end up containing at least two balls because there aren't enough boxes for every ball. This common scenario illustrates how the Pigeon-Hole Principle applies to everyday situations.

So the generalized pigeon-hole principle is the following: So imagine you have N objects, in this case you had N pigeons, and suppose those N objects are assigned to K boxes in a random fashion, then the pigeon-hole principle states that there will be at least 1 box which will have ⌈N/K⌉ many objects.

The generalized version of the Pigeon-Hole Principle extends the basic idea to any number of objects and boxes. It states that if you distribute N objects into K boxes, then at least one box will contain at least ⌈N/K⌉ objects. The ceiling function (⌈x⌉) rounds up to the nearest integer, meaning if N is not perfectly divisible by K, some boxes will contain more items than others, demonstrating that at least one will exceed this average.

Consider you have 20 apples to distribute among 6 baskets. According to the generalized Pigeon-Hole Principle, at least one basket will contain at least ⌈20/6⌉ = ⌈3.33⌉ = 4 apples. This leads to the effective conclusion that no matter how you distribute the apples, at least one basket must hold 4 or more.

So let's see an application of pigeon-hole principle. […] Then our claim is that irrespective of the way the people are mutually friends or enemies there always exists either 3 mutual friends in the party or 3 mutual enemies.

A scenario illustrates that if you have 6 people at a party, each pair can either be friends or enemies. The Pigeon-Hole Principle helps us prove that among these 6 people, there will always be either 3 who are friends with each other or 3 who are enemies. By selecting one person and analyzing their relationships with the remaining 5, we can categorize them into friends and enemies, leading us inevitably to conclude that one of these relationships must dominate (three mutual friends or three mutual enemies) due to the sheer number of individual relationships involved.

Imagine a small gathering where you know that everyone either knows each other well (friends) or doesn’t (enemies). If there are 6 attendees, despite how those relationships unfold, you will always find either a trio that knows each other or a trio that doesn't. It's reminiscent of group dynamics in classrooms where any mix of students will form either friendships or cliques that can be analyzed using the Pigeon-Hole Principle.

--