The Pigeon-Hole Principle 257
Since F(xl) = F(x 2 ), F(xl) and F(x 2 ) account for one element in range(F). The elements
F(x 3 ), F(x 4 ) ..... F(xn)
account for at most n - 2 more. That leaves at most n - 1 elements in range(F). Since Y
has n elements, range(F) is not all of Y, so F is not onto. 0
Theorem 6. Let X and Y be sets and X be finite. Let F : X --* Y be 1-1 and onto. Then,
Y is finite, and I X I = I Y 1.
As an example of applying Theorem 6, suppose a professor enters a classroom that she
knows contains 55 chairs. Now, suppose the professor can see that all students are seated,
no chairs are empty, and no chair has two people sitting in it. If the professor wants to
know how many students are seated in the room, it is not necessary to count them. Let
the function SeatOf map each student to the chair that student occupies. The professor has
observed that SeatOf is 1-1 and onto. Therefore, the number of students equals the number
of chairs: 55.
4.6.3 Application: Decimal Expansion of Rational Numbers
We will present several examples and prove several theorems that are applications of the
Pigeon-Hole Principle. These results are interesting in their own right, but they also give
insight regarding possible applications of the Pigeon-Hole Principle.
The first application concerns converting fractions to decimals or, in more formal lan-
guage, expressing rational numbers as decimals. A rational number of the form
0.di d2 ... dndi di +l ... dndidi+j ...' d, '
with the digits didi+l ... d, repeating is denoted as
0.dld2 ... di-ldidi+l ... d.
The following are examples of the conversion of a fraction to a decimal with the special
notation for the repeated digits:
1
- = 0.1 = 0. 10000... 00 ... = 0.10
10
102
- 4.08 = 4.08000.. ... =0. 4.080
25
1
-- = 0.333333 ... 33 .... = 0.3
3
2 = 0.181818... 1818 ... =0.18
11
The decimal expansions of 1/10 and 102/25 are finite or terminating. All but a fi-
nite number of their decimal digits are 0. The decimal expansions of 1/3 and 2/11 are
nonterminating or infinite. All these decimal expansions are repeating: After a certain
point, the decimal expansion can be generated by repeating a block of digits infinitely many
times. The decimal expansions of 1/10 and 102/25 have repeating O's. The expansion of
1/3 has repeating 3s. The expansions of 2/11 has the two digits, 18, repeating. There are
some rationals that have two repeating decimal expansions, such as 1.0000... and 0.9. (See
Exercise 14 in Section 4.5.)
