Given Any Set of 15 Integers, Must There Be Two

Question

Examlex · Accepted Answer

The Answer is Yes.
Solution 1: There are 12 possible remainders that can be obtained when an integer is divided
by 12, namely 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11. Apply the pigeonhole principle, thinking of the elements of the set of 15 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 12. Since 15 > 12, 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 12.
Solution 2: Let

X

be the set of fifteen integers and

Y

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

R

from

X

(the pigeons) to

Y

(the pigeonholes) defined by the rule:

R ( n ) = n \bmod 12 ( =

the remainder obtained by the integer division of

n

by 12). Now

X

has 15 elements and

Y

has 12 elements

( 0,1,2,3,4,5,6,7,8

,

9,10,11 )

. 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 12 .

Given Any Set of 15 Integers, Must There Be Two

Definitions: