Section 005) Pigeonhole Principle

Introduction

Pigeonhole principle simply states that if n+1 pigeons occupy n containers then one container shall have at least 2 pigeons.

As an example if you have socks of 2 colors and you pick 3 socks then at least 2 socks shall be of same color

If there are 13 persons in a room then 2 persons are born in the same month.

We now solve a couple of problems based on Pigeonhole principle

Problem  1

Show that inside  a square of radius 2 if we have 5 points then there are 2 points distance between them is less than $\sqrt{2}$.

Solution 1

Divide the square into 4 squares of size 1. As we have 5 points in 4 squares(edges includes) there are at least 2 points in one square. distance between 2 points inside the square is less than $\sqrt{2}$


Problem  2

 If you pick 51 numbers from the numbers 1 to 100 then there are 2 numbers whose sum is 101.

Solution 2

We can make 50 sets (1,100), (2,99), (3, 98) .... (50,51).

Now if we chose 51 numbers from the above 50 sets then 2 numbers must belong to same  set and and the sum shall be 101.