Discrete Mathematics for Computer Science

The Pigeon-Hole Principle 259

r = 0.4579909909909909... 909909...

with repeating block of digits 909. It is easier to work with expansions in which the repeat-

ing part appears beginning immediately to the right of the decimal point. To accomplish

this proof, we will need to multiply the decimal by some power of 10. This is really just

for our convenience and does not affect the proof.

If the repeating part has length k that begins j digits to the right of the decimal point,

multiply r by 1 0j+k. In the illustration,

107 .r = 4579909.909909909... 909 ....

Now, multiply r by 10', and subtract the product from 10 +k • r, giving d = (IOj+k -

10') • r. In the illustration,

107 r = 4579909.909909909909... 909...

• 104 r = -4579.909909909909... 909...

(107 - 104) r = 4575330.000000000000... 000...

Since all digits past the decimal point match, the subtraction results in all O's to the right of

the decimal point. Therefore, the difference d is an integer. It follows from this computation

that r = d/(lOj+k - 10'). Therefore, r is a rational number. U

4.6.4 Application: Problems with Divisors and Schedules

In scenarios as diverse as studying for exams or finding divisors of sums of numbers, the

Pigeon-Hole Principle can provide answers to many questions.

Example 4. Let m E N. Given m integers al, a2 .... am, there exist k and I with 0 <

k <1 <m such that

ak+1 + ak+2 + + + al

is divisible by m.

Solution. Consider the m sums:

al,al +-a2, al +-a2 +-a3 ... , al +-a2 +,,. +-am

If any of these sums is divisible by m, then the conclusion follows. If not, then we may sup-

pose that each sum has a nonzero remainder when divided by m. The possible remainders

are

Since there are m sums and only m - 1 possible remainders, at least two of the sums must
have the same remainder when divided by m (according to the Pigeon-Hole Principle).
Therefore, there are integers k and 1 with 1 > k such that

al +a2+.'.+ak

and

al +a2 + + al