Given Any Set of 30 Integers, Must There Be Two

Question

Examlex · Accepted Answer

The Answer is Yes.
Solution 1: There are 25 possible remainders that can be obtained when an integer is divided by 12, namely all the integers from 0 through 24. Apply the pigeonhole principle, thinking of the elements of the set of 30 integers as the pigeons and the possible remainders as the pigeonholes. Each pigeon ﬂies into the pigeonhole that is the remainder obtained when it is divided by 25. Since 30 > 25, the pigeonhole principle says that at least two pigeons must ﬂy into the same pigeonhole. So at least two of the numbers must have the same remainder when divided by 25.
Solution 2: Let

X

be the set of 30 integers and

Y

the set of all possible remainders obtained through division by 30 , and consider the function

R

from

X

(the pigeons) to

Y

(the pigeonholes) defined by the rule:

R ( n ) = n \bmod 25

(= the remainder obtained by the integer division of

n

by 25). Now

X

has 30 elements and

Y

has 25 elements (the integers from 0 through 24). Hence by the pigeonhole principle,

R

is not one-to-one:

R \left( n _ { 1 } ight) = R \left( n _ { 2 } ight)

for some integers

n _ { 1 }

and

n _ { 2 }

with

n _ { 1 } eq n _ { 2 }

. But this means that

n _ { 1 }

and

n _ { 2 }

have the same remainder when divided by 25 .

Given Any Set of 30 Integers, Must There Be Two

Definitions: