Problem of the Week 800:
The Glove Shortage
A disaster has just occured and hospital has to operate on a number of
patients and they are so busy that all doctors have to assist with all
operations. Now, all patients may be suffering from some contagious
disease, and all doctors may have picked up some contagious diseases
in the hospital. In order to prevent the spread of disease, each doctor
must wear operating gloves, but in order to minimize cost, he can reuse
gloves under the conditions that
- Each doctor either uses a clean glove surface, or a surface
that only he has come in contact with.
- Each patient is operated on by a glove with a clean outside
surface or one that only he has been exposed to.
For the following values of m doctors and n patients, what is the minimum
number of gloves needed?
- m = n = 2.
- m = 3, n = 1.
- m = n = 6.
You are allowed to
- Nest gloves (note that nesting a clean surface in an exposed
surface will lead to contamination).
- Turn gloves inside out.
Back to the Fall 1995 PotW Archive.
© Copyright 1996 Stan Wagon. Reproduced with permission.
Jeff Erickson
(jeffe@cs.berkeley.edu)
Last update: 20 Feb 96