Re: Combinatorics 'Designated Driver' Problem
- From: israel@xxxxxxxxxxx (Robert Israel)
- Date: 10 Feb 2006 20:52:16 GMT
In article <1139549626.132245.272130@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Garrett Baird <garrettbaird2@xxxxxxxxxxx> wrote:
Hi,
Last week at math team, we came across this problem, which noone could
solve. Can anybody suggest anything?
Suppose we have a set of N people, and every night, a certain subset
of them like to go out drinking. For example on the first night,
{1,3,5} go out, then on the next night, {4,6,2,5,8} go out, and so on
and so forth, for D days. We have a schedule drawn for us, so on each
day we know exactly who will go out (best illustrated by a bipartite
graph).
Now, each time these people go out, somebody will need to be a
designated driver. We want to find some way to assign a driver to
each day. Of course, we have to be fair about how we make this
assignment. So, what we do is the following:
For each person i, look at each day on which they go drinking.
For each of these days, add 1/(total number of people who go
drinking that day)
The sum S_i of these reciprocals is the maximum number of days
this
person should drive. Since S_i is not generally an integer, we round
S_i upward to the nearest integer.
Our problem was to prove that a driving schedule exists, in which each
person drives at most S_i times. We drew a lot of graphs, but did not
come up with anything. One person said it could probably be done as a
"max-flow min-cut" problem, so maybe that's some kind of lead, but I'd
really like to know how this problem works.
Yes, it can be done that way.
Consider the bipartite directed graph with source vertices corresponding
to the people and sink vertices corresponding to the days, with an arc
from person i to day d if i goes out on day d. The source i can supply
S_i units of flow, and sink d demands 1 unit. Let E_d be the set of
people that go out on day d, and for any set B of days,
E_B = union_{d in B} E_d the set of people that go out on at least one of
the days in B. By the max-flow=min-cut theorem, all demands can be
satisfied if and only if for each set B of days,
sum_{i in E_B} S_i >= |B|. And it's not hard to prove this inequality.
Note that by the Integrality Theorem, since the supplies and demands are
all integers there will be a solution where the flows in all arcs are
integers, and thus correspond to a selection of a driver for each day:
person i drives on day d if the flow from i to d is 1.
Robert Israel israel@xxxxxxxxxxx
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
.
- References:
- Combinatorics 'Designated Driver' Problem
- From: Garrett Baird
- Combinatorics 'Designated Driver' Problem
- Prev by Date: Re: Proving Infinimums
- Next by Date: Re: understanding the definiton of limits
- Previous by thread: Combinatorics 'Designated Driver' Problem
- Next by thread: actuarial exam= probability problem
- Index(es):
Relevant Pages
|
