Pigeonhole Principle Proof Generalized

830 Views Asked by At

An airport sees 1500 takeoffs per day. Prove that there are two planes that leave within a minute of each other.

All I can get started with is finding the total minutes in a day- 1440min. I understand that I have to fit 1500 planes into 1440 boxes however I do not know how to use this to prove that at least 2 planes leave within a minute of each other. Kindly help.

2

There are 2 best solutions below

0
On

The Pigeonhole Principle seems to be the perfect approach.

Let the 1440 minutes be the pigeonholes and the 1500 takeoffs be the pigeons. It follows that $$\text{At least } \left\lceil\frac{1500}{1440}\right\rceil=2\text{ planes take off in the same minute}$$

0
On

Imagine the day as divided into $1440$ one-minute intervals. Those will be your pigeonholes. The $1500$ planes are your (high-tech) pigeons. Think of a plane (= pigeon) leaving within a particular minute (= pigeonhole) as putting that pigeon in that hole. The pigeonhole principle says there must be two pigeons in a single hole. Given the nature of your pigeons, holes, and "pigeon being in a hole", this means that there must be two planes leaving in the same one-minute interval.

In general, when applying the pigeonhole principle to problems like this, you should look for ways to interpret "pigeon", "hole", and "pigeon being in a hole" in ways relevant to your problem, so that the conclusion of the pigeonhole principle, "at least two pigeons in the same hole" gets interpreted as the conclusion you want.