Thread: generalised pigeonhole principle

Hello,

The generalised pigeonhole principle is proved by using contradiction. The proof is given below.

consider there are no pigeonholes that contain more than ceil(m/n) - 1.

Then the total number of pigeons m <= n * ceil(m/n)-1
m < n*(m/n) + 1 - 1
m = m which is a contradiction.


Can anyone please tell how it is a contradiction.

Originally Posted by sudeepmansh

Hello,

The generalised pigeonhole principle is proved by using contradiction. The proof is given below.

consider there are no pigeonholes that contain more than ceil(m/n) - 1.

Then the total number of pigeons m <= n * ceil(m/n)-1
m < n*(m/n) + 1 - 1
m = m which is a contradiction.


Can anyone please tell how it is a contradiction.

I think there is an error in what you wrote.

"m = m which is a contradiction"

it has to be m < m which is a contradiction. This follows directly from the preceding step.