Glove Problem

Let there be m doctors and n<=m patients, and let all mn possible combinations of examinations of patients by doctors take place. Then what is the minimum number of surgical gloves needed G(m,n) so that no doctor must wear a glove contaminated by a patient and no patient is exposed to a glove worn by another doctor (where it is assumed that each doctor wears a glove on a single hand only)? In this problem, the gloves can be turned inside out and even placed on top of one another if necessary, but no "decontamination" of gloves is permitted. The optimal solution is

 g(m,n)={2   m=n=2; 1/2(m+1)   n=1, m=2k+1; [1/2(m)+2/3n]   otherwise,

where [x] is the ceiling function (Vardi 1991).

The case m=n=2 is straightforward since two gloves have a total of four surfaces, which is the number needed for mn=4 examinations. With doctors AB, patients ab, and gloves 12, a solution is A12a, A1b, B2a, B21b.

See also

Cocktail Party Graph, Handshake Problem, Party Problem

Explore with Wolfram|Alpha


Gardner, M. Aha! Insight. New York: Scientific American, 1978.Gardner, M. Science Fiction Puzzle Tales. New York: Crown, pp. 5, 67, and 104-150, 1981.Hajnal, A. and Lovász, L. "An Algorithm to Prevent the Propagation of Certain Diseases at Minimum Cost." §10.1 in Interfaces Between Computer Science and Operations Research: Proceedings of a Symposium Held at the Mathematisch Centrum, Amsterdam, September 7-10, 1976 (Ed. J. K. Lenstra, A. H. G. Rinnooy Kan, and P. van Emde Boas). Amsterdam: Matematisch Centrum, 1978.Orlitzky, A. and Shepp, L. "On Curbing Virus Propagation." Exercise 10.2 in Technical Memo. Bell Labs, 1989.Vardi, I. "The Condom Problem." Ch. 10 in Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, pp. 203-222, 1991.

Referenced on Wolfram|Alpha

Glove Problem

Cite this as:

Weisstein, Eric W. "Glove Problem." From MathWorld--A Wolfram Web Resource.

Subject classifications