Discrete Mathematics

254

DISCRETE

MATHEMATICS'-------------------------

An equivalent way

of

stating the principle is:

If

n pigeons are placed in r holes, then there is at least one

hole with

r n I r l pigeons

in

it.

Example

I

We

will prove that there are at least

200

Indians with exactly the same number

of

hair

on

their

heads. First

we

estimate that the number

of

hairs

on

any persons's head is at the most a million. There are

more than

200

million Indians.

To

apply the strong pigeonhole principle, think

of

Indians as pigeons, and

that there is a hole for each unique number

of

possible

hair

that is, all Indians with the same number

of

hairs

go

into

the

same

hole. ...