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 x1 > x2 > x3 > x4, and the afternoon routes have lengths y1 > y2 > y3 > y4. 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 x1 > x2 > x3 > x4, followed by cleaning chores of lengths y1 > y2 > y3 > y4. 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 x1+y4, x2+y3, x3+y2, x4+y1. 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
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 x1 + x2 + y1 + y2 – 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 (x1 +y1, x2 + y2) will pay for x1 + y1 – H overtime hours. We need to compare this with the suggested assignment whose overtime hours is at most (x1 + y2 – H) + (x2 + y1 – H) = (x1 + y1 – H) + (x2 + y2 – H). The sum on the right is at most x1 + y1 – 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
x1+y4, x2+y3, x3+y2, x4+y1. 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 (x1, x2, x3, x4) = (y1, y2, y3, y4) = (4, 3, 2, 1) and let H = 4. Then the maids schedule (x1+y4, x2+y3, x3+y2, x4+y1) = (5, 5, 5, 5) results in all four cooks receiving tickets. The alternative schedule (x1+y1, x2+y4, x3+y3, x4+y2) = (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.