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 ) = { 2 M = N = 2 1 2 ( M + 1 ) N = 1 , M odd ⌈ M 2 + 2 N 3 ⌉ otherwise, {\displaystyle 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 ⌈ x ⌉ {\displaystyle \lceil x\rceil } is the ceiling function. Hajnal and Lovász proved a lower bound of ⌈ M / 2 + 2 N / 3 − 1 / 3 ⌉ {\displaystyle \lceil M/2+2N/3-1/3\rceil } for all M, N and an upper bound of ⌈ M / 2 + 2 N / 3 ⌉ + 1 {\displaystyle \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.
… excerpt ends here. Continue reading the full article.
