Page 346 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 325

the last talk scheduled in the main lecture hall has ended. Note that a talk with the earliest end
time is always selected first by the algorithm. We will show that this greedy algorithm is optimal
in the sense that it always schedules the most talks possible in the main lecture hall. To prove
the optimality of this algorithm we use mathematical induction on the variable n, the number
of talks scheduled by the algorithm. We let P (n) be the proposition that if the greedy algorithm
schedules n talks in the main lecture hall, then it is not possible to schedule more than n talks
in this hall.
BASIS STEP: Suppose that the greedy algorithm managed to schedule just one talk, t 1 ,in
the main lecture hall. This means that no other talk can start at or after e 1 , the end time of t 1 .
Otherwise, the first such talk we come to as we go through the talks in order of nondecreasing
end times could be added. Hence, at time e 1 each of the remaining talks needs to use the main
lecture hall because they all start before e 1 and end after e 1 . It follows that no two talks can be
scheduled because both need to use the main lecture hall at time e 1 . This shows that P(1) is
true and completes the basis step.
INDUCTIVE STEP: The inductive hypothesis is that P(k) is true, where k is an arbitrary
positive integer, that is, that the greedy algorithm always schedules the most possible talks
when it selects k talks, where k is a positive integer, given any set of talks, no matter how
many. We must show that P(k + 1) follows from the assumption that P(k) is true, that is, we
must show that under the assumption of P(k), the greedy algorithm always schedules the most
possible talks when it selects k + 1 talks.
Now suppose that the greedy algorithm has selected k + 1 talks. Our first step in completing
the inductive step is to show there is a schedule including the most talks possible that contains
talk t 1 , a talk with the earliest end time. This is easy to see because a schedule that begins with
the talk t i in the list, where i> 1, can be changed so that talk t 1 replaces talk t i . To see this, note
that because e 1 ≤ e i , all talks that were scheduled to follow talk t i can still be scheduled.
Once we included talk t 1 , scheduling the talks so that as many as possible are scheduled
is reduced to scheduling as many talks as possible that begin at or after time e 1 . So, if we
have scheduled as many talks as possible, the schedule of talks other than talk t 1 is an optimal
schedule of the original talks that begin once talk t 1 has ended. Because the greedy algorithm
schedules k talks when it creates this schedule, we can apply the inductive hypothesis to conclude
that it has scheduled the most possible talks. It follows that the greedy algorithm has scheduled
the most possible talks, k + 1, when it produced a schedule with k + 1 talks, so P(k + 1) is
true. This completes the inductive step.
We have completed the basis step and the inductive step. So, by mathematical induction we
know that P (n) is true for all positive integers n. This completes the proof of optimality. That is,
we have proved that when the greedy algorithm schedules n talks, when n is a positive integer,
then it is not possible to schedule more than n talks. ▲

CREATIVE USES OF MATHEMATICAL INDUCTION Mathematical induction can often
be used in unexpected ways. We will illustrate two particularly clever uses of mathematical
induction here, the first relating to survivors in a pie fight and the second relating to tilings with
regular triominoes of checkerboards with one square missing.
EXAMPLE 13 Odd Pie Fights An odd number of people stand in a yard at mutually distinct distances.
At the same time each person throws a pie at their nearest neighbor, hitting this person. Use
mathematical induction to show that there is at least one survivor, that is, at least one person
who is not hit by a pie. (This problem was introduced by Carmony [Ca79]. Note that this result
is false when there are an even number of people; see Exercise 75.)

Solution: Let P(n) be the statement that there is a survivor whenever 2n + 1 people stand in
a yard at distinct mutual distances and each person throws a pie at their nearest neighbor. To
prove this result, we will show that P(n) is true for all positive integers n. This follows because
as n runs through all positive integers, 2n + 1 runs through all odd integers greater than or equal