Discrete Mathematics for Computer Science

260 CHAPTER 4 Functions

have the same remainder r when divided by m. That is, there are integers c, d, and r such

that

al +a2 +'+'ak =cm +r

and

al+a2±+'+al =dm + r

Subtracting the k-element sum from the i-element sum gives

ak+4 + ak+2 + + al = (d - c)m

Therefore,

ak+1 + ak+2 + + al

is divisible by m. U

Example 5 shows how a scheduling decision can be better understood.

Example 5. The local softball league wants to schedule at least one game every day

during the 11-week summer season. To keep the fields in good condition, it is decided to

schedule no more than 12 games in any week. Show that there is a succession of days

during which exactly 21 games are scheduled.

Solution. Let al be the number of games scheduled for day 1. In general let ai where

1 < i < 77 be the total number of games played on days 1 through i. The sequence of

numbers a I, a2 .... a77 is strictly increasing since at least one game is played each day.

Since al > 1 and at most 12 games are played in a week, we have a77 < 132. The se-

quence al + 21, a2 + 21 ... , a77 + 21 is also an increasing sequence. Each of the 154

numbers al, a2 ... , a77, al + 21, a2 ± 21 .... a77 + 21 is an integer between l and 153.

Since there are 154 numbers, then by the Pigeon-Hole Principle, two of them must be

equal. No two of the numbers al, a2 ... , a77 are equal, however, and no two of the num-

bers al + 21, a2 + 21 .... a77 + 21 are equal. Therefore, there are i and j such that

ai = aj + 21

Thus, on days aj+l, aj+2. ai, 21 games are scheduled. U

It would be nice if we knew how many days were used for these 21 games. The only

thing we can say for sure is that the number of days is no more than 21 and no less than 11.

In 7 days 12 games can be played. During a second week an additional 12 games can be

played. Since at least one game must be played each day, a total of 21 games cannot occur

in fewer than 11 days.

4.6.5 Application: Two Combinatorial Results

The two results included here are probably surprising as far as finite sequences of natu-

ral numbers. The first proves that two elements of certain finite sequences must have the

property that one divides the other. The second proves that some sequences always have

an increasing or decreasing subsequence that is at least of a length given as a function of

the number of elements in the sequence. Both of these results are credited to the eminent

mathematician Paul Erdds (1913-1996, b. Hungary).