Glove problem

In operations research and combinatorics, the glove problem (also known as the condom problem) is an optimization problem asking for the minimum number of two-sided protective barriers needed for every member of one group to interact with every member of another without any barrier surface being exposed to two different people. It first appeared in print, in the form of doctors, patients and surgical gloves, in Martin Gardner's column in Isaac Asimov's Science Fiction Magazine. It is also used as an example that the cheapest capital cost often leads to a dramatic increase in operational time, but that the shortest operational time need not be given by the most expensive capital cost.

Problem statement

M doctors are each to examine each of N patients, wearing gloves to avoid contamination, giving MN examinations in total. Gloves may be reused any number of times, turned inside out, and worn several at a time, but no decontamination is permitted: once a surface has been contaminated it remains so permanently, and a surface becomes contaminated whether by contact with a person or by contact with an already-contaminated surface. The requirement is that no doctor wear a glove contaminated by a patient, and no patient be exposed to a glove worn by another doctor.

A naive approach would use MN gloves, one per examination. This can be reduced substantially by exploiting the fact that each glove has two sides and that both sides need not be used simultaneously: giving every participant a single glove for the entire operation, so that each encounter is protected by a double layer and the outer surface of a doctor's glove meets only the inner surface of a patient's, already brings the count down to M + N.

Solution

Assume without loss of generality that M ≥ N. The minimum number of gloves G(M, N) required for all the doctors to examine all the patients is

$G(M,N)={\begin{cases}2&M=N=2\\[4pt]{\tfrac {1}{2}}(M+1)&N=1,\ M{\text{ odd}}\\[4pt]\left\lceil {\dfrac {M}{2}}+{\dfrac {2N}{3}}\right\rceil &{\text{otherwise,}}\end{cases}}$

where $\lceil x\rceil$ is the ceiling function. Hajnal and Lovász proved a lower bound of $\lceil M/2+2N/3-1/3\rceil$ for all M, N and an upper bound of $\lceil M/2+2N/3\rceil +1$ when M = N = 6k, leaving a gap of one; Vardi closed it by constructing the required "master glove" from gloves already in use rather than adding an extra one.

The two exceptional cases are the original formulations of the puzzle, and both are settled by counting surfaces. For M = N = 2, two gloves provide four clean surfaces for four people. For N = 1 and M = 2k + 1, the k + 1 gloves are again exactly half the number of participants. The case M = 3, N = 1 – three doctors, one patient, two gloves – is the version given by Martin Gardner.

Graph formulation

The analysis of Hajnal and Lovász, followed by Vardi, represents a protocol as a directed graph whose vertices are the participants and whose edges are the gloves. If one side of a glove is first contaminated by person D₁ and the other side subsequently by person D₂, a directed edge is drawn from D₁ to D₂; simultaneous contaminations and permanently clean sides are directed arbitrarily.

The efficiency of a protocol is determined by the connected components of this graph. The most efficient component is $D_{1}\to D_{2}$, in which one person uses a glove for all encounters and then passes it on inverted: two people, one glove. The next most efficient is $D_{1}\to D_{2}\to D_{3}$: three people, two gloves. Because a person must complete all encounters before passing a glove on, components of the first kind cannot occur among the doctors and the patients simultaneously. An optimal protocol therefore assigns the cheaper two-person components to whichever group is more numerous and three-person components to the other, which is the origin of the coefficients ⁠1/2⁠ and ⁠2/3⁠.

Makespan

Assigning each participant a single glove for the entire operation, so that every encounter is protected by a double layer, uses M + N gloves. The makespan with this scheme is K · max(M, N), where K is the duration of one pairwise encounter. Note that this is exactly the same makespan if MN gloves were used. Clearly in this case, increasing capital cost has not produced a shorter operation time. Schemes using fewer gloves rely on gloves being planted, passed and collected in sequence, and have correspondingly longer makespans; which scheme is preferable depends on the cost of a glove relative to the cost of a longer operation.

Generalizations

Vardi poses several extensions. One asks for the analogous formula when every pair of individuals interacts, rather than only doctor–patient pairs. Another, attributed to A. Orlitzky and L. Shepp, treats M men and N women with M ≥ N where all the men are bisexual. The most general form replaces the complete bipartite graph of required encounters by an arbitrary preference graph, in which two people interact if and only if they are joined by an edge; Vardi marks this case as difficult.