The town has four meter maids. They work
both a morning and an afternoon shift, and they all work at about
the same speed. The morning routes have lengths x_{1} > x_{2} > x_{3} > x_{4},
and the afternoon routes have lengths y_{1} > y_{2} > y_{3} > y_{4}.
Any meter maid who works more than H hours has the extra hours paid
in overtime.

Incidentally, they all meet for lunch
at the local doughnut shop where the four cooks experience a similar
situation: To come to work they must park their scooters in the street,
where the parking meters have a time limit of H hours. Their workday
consists of baking chores of lengths x_{1} > x_{2} > x_{3} > x_{4},
followed by cleaning chores of lengths y_{1} > y_{2} > y_{3} > y_{4}.
The shop pays the parking tickets of the cooks whose workday has
more than H hours.

Show that the best way to assign a morning
and afternoon route to each meter maid in order to minimize overtime
is x_{1}+y_{4}, x_{2}+y_{3}, x_{3}+y_{2},
x_{4}+y_{1.} Is that necessarily also the best assignment
for the cooks as well?'

Solution to MP36

We
received a correct solution from Patrick LoPresti (USA), who based
his argument on two simple preliminary observations. The first describes
an algorithm he
calls the naive bubble sort algorithm.

Observation 1. Given any sequence of N real numbers a1,
a2, ..., aN, the following algorithm will always halt, and when it
does the sequence will be sorted in nonincreasing order.

Step 1.

.If every adjacent pair of elements is in order
(that is, if ai ≥ ai+1 for i from 1 to N–1) then
halt.

Step 2.

Else, find an adjacent pair of numbers which are out of order
and exchange them.

Proof.

If the sequence is not sorted, then at least
one element is out of order: aj is less than ak for j < k.
The first element that is out of order will, by definition, be
preceded by a smaller element.
Simply exchange them and the number of pairs that are out of order
decreases by one. Since the number of pairs is finite, the algorithm
ends when no pairs are out of order. Simply exchange them and the
number of pairs, adjacent or not, that are out of order decreases
by one. Since the total number of pairs is finite, the algorithm
ends when no pairs are out of order.

Observation 2. The analogue of the problem when there
are only two meter maids is easy. More precisely, if

a.

there two morning shifts with x1 > x2,

b.

two afternoon shifts with y1 > y2, and

c.

any work beyond H hours is overtime,

then to minimize overtime the suggested
schedule (x1 + y2, x2 + y1) is as good
or better than the alternative schedule (x1 +y1, x2 + y2).

Proof.

A nice way to organize all the information
is in a 2-by-2 matrix whose columns are labeled x1 and x2,
and whose
rows are labeled
y1 and y2. The entry in column i, row j is the larger between
xi + yj – H and 0, namely the hours of overtime that
comes with the assignment xi and yj. We must assign to each
meter maid a row
and column so

x_{1}

x_{2}

y_{1}

max{x_{1} + y_{1} – H,
0}

max{x_{2} + y_{1} – H,
0}

y_{2}

max{x_{1} + y_{2} – H,
0}

max{x_{2} + y_{2} – H,
0}

that each row and column has one name in it. We
know (from conditions (a) and (b)) that

.

Thus, if the entry
in the first row and column
is 0 then all entries of the matrix are zero (because H is larger
than any assignment); no overtime is paid, no matter how the
shifts are assigned. This means that the suggested assignment
is as good
as the alternative. Also if no entry is 0, both assignments are
equally bad: the total amount of overtime hours would be x_{1} + x_{2} +
y_{1} + y_{2} – 2H whichever schedule is used. The question comes
down to what happens when the upper left entry is nonzero and the
lower right entry is zero. The alternative assignment (x_{1} +y_{1},
x_{2} + y_{2}) will pay for x_{1} + y_{1} – H overtime hours. We need
to compare this with the suggested assignment whose overtime hours
is at most

The sum on the right is at most x_{1} + y_{1} – H
because the last term is at most 0. Of course, either or both
of the two terms on the left could be zero. In other words, the
suggested assignment provides either the same or fewer overtime
hours, and we again see that it is at least as good as the alternative.

This
completes the proof of the second observation.

By combining our two observations, the result follows
easily. Without loss of generality we fix the morning assignments.
Our goal is to assign the afternoon routes to minimize overtime.
Start by pairing each x with a y by any method you wish. Find an
adjacent pair whose afternoon routes are “out of order;” that
is, xs is paired with yi, and xt paired with yj, but s < t and
i < j. This pair of maids meets the conditions for observation
2, so we can swap their afternoon routes without increasing the
overtime. By the first observation this process eventually terminates
with the afternoon routes in the suggested order with the assignments
x_{1}+y_{4}, x_{2}+y_{3}, x_{3}+y_{2}, x_{4}+y_{1}. Note that the argument generalizes
to an arbitrary number of meter maids.

For the second part of the
question, the answer is no, the maids assignment need not be
the best for the cooks. Here is a simple counterexample. Let (x_{1}, x_{2}, x_{3}, x_{4}) = (y_{1}, y_{2}, y_{3}, y_{4}) = (4, 3, 2, 1) and let H = 4. Then the maids schedule
(x_{1}+y_{4}, x_{2}+y_{3}, x_{3}+y_{2}, x_{4}+y_{1}) = (5, 5, 5, 5) results in all four cooks receiving
tickets. The alternative schedule (x_{1}+y_{1}, x_{2}+y_{4}, x_{3}+y_{3}, x_{4}+y_{2}) = (8, 4, 4, 4) results in just one cook receiving a ticket.

Our November problem was inspired
by a problem from Introduction to Graph Theory, by Douglas B.
West. It comes in a
chapter discussing how graphs can be used to solve minimum weight
matching problems. West’s message seems to be that you do
not always use your big machinery on all problems.