Fun Application of pigeonhole principle

Author Topic: Fun Application of pigeonhole principle  (Read 1497 times)

Offline Masuma Parvin

  • Sr. Member
  • ****
  • Posts: 323
    • View Profile
Fun Application of pigeonhole principle
« on: November 13, 2012, 03:48:15 PM »
In a group of six people, there will always be three people that are mutual friends or mutual strangers. (Assume that “friend” is symmetric-if x is a friend of y, then y is a friend of x.)

The problem can be thought of geometrically. Imagine the six people as points and let an edge between points indicate friendship. No matter how the graph is drawn, we want to show there is a set of three points that are all connected or a set of three points that has no connecting edges.

Consider any single point. There are five other points it could possibly connect to. By the pigeonhole principle, the point is either connected to at least three other points or not connected to at least three other points.

Case 1: the point is connected to (at least) three other points
If any of these points are connected to each other, then we have found a triangle of three mutual friends. (These two points are connected, plus they are both connected to the original point).

Otherwise, that means none of these three points are connected and hence they are mutual strangers. This would be a set of three points without any edges.

Case 2: the point is not connected to (at least) three other points
If any of these points are not connected to each other, then we have found a triangle of three mutual strangers. (These two points are not connected, plus they are both not connected to the original point).

Otherwise, that means all of these three points are connected and hence they are mutual friends. This would be a set of three points with all connecting edges.

Offline msu_math

  • Jr. Member
  • **
  • Posts: 81
    • View Profile
Re: Fun Application of pigeonhole principle
« Reply #1 on: November 13, 2012, 05:02:53 PM »
Great! A real word application of the Pigeonhole Principle.
Mohammad Salah Uddin

Lecturer in Mathematics
Department of Natural Sciences
FSIT, DIU

Offline snlatif

  • Faculty
  • Sr. Member
  • *
  • Posts: 267
    • View Profile
Re: Fun Application of pigeonhole principle
« Reply #2 on: November 14, 2012, 02:52:48 PM »
Thanks for sharing this real world example,madam... :)