Glove problem

M doctors are each to examine each of N patients, wearing gloves to avoid contamination. Each glove can be used any number of times, but the same side of one glove cannot be exposed to more than one person. Gloves can be re-used any number of times, and more than one can be used simultaneously.

Given M doctors and N patients, the minimum number of gloves G(M, N) required for all the doctors to examine all the patients is given by:

• G(M, N) = M + N − 2 if both M, N ≥ 2
• G(M, 1) = M
• G(1, N) = N
• G(1, 1) = 1

A naive approach would be to estimate the number of gloves as simply G(M, N) = MN. But this number can be significantly reduced by exploiting the fact that each glove has two sides, and it is not necessary to use both sides simultaneously.

A better solution can be found by assigning each person his or her own glove, which is to be used for the entire operation. Every pairwise encounter is then protected by a double layer. Note that the outer surface of the doctor's gloves meets only the inner surface of the patient's gloves. This gives an answer of M + N gloves, which is significantly lower than MN.

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.

The number G(M, N) may be refined further by allowing asymmetry in the initial distribution of gloves. The best scheme is given by:

• Doctor # 1 wears N gloves, layered one on top of another. He visits the N patients in turn, leaving the outermost glove behind with each.
• Doctors # 2 to (M − 1) wear one glove each, and follow the double-layered protocol at each interaction, as described above.
• Doctor # M doesn't wear one of his own, but he visits all the N patients, collecting their gloves in turn and turning it into a multilayered glove progressively. Note that in his first encounter, he uses only the untouched inside of Patient # 1's glove, so it's still safe.

This scheme uses (1 · N) + ((M − 1 − 1) · 1) + (1 · 0) = M + N − 2 gloves. This number cannot be reduced further.

The makespan is then given by:

• N serial interactions to plant the gloves.
• max(M − 2, N) parallelized interactions for intermediate stage.
• N serial interactions to collect the gloves.

Makespan: K · (2N + max(M − 2, N)).

Clearly, the minimum G(M, N) increases the makespan significantly, sometimes by a factor of 3. Note that the benefit in the number of gloves is only 2 units.

One or the other solution may be preferred depending on the relative cost of a glove judged against the longer operation time. In theory, the intermediate solution with (M + N − 1) should also occur as a candidate solution, but this requires such narrow windows on M, N and the cost parameters to be optimal that it is often ignored.

The statement of the problem does not make it clear that the principle of contagion applies, i.e. if the inside of one glove has been touched by the outside of another that previously touched some person, then that inside also counts as touched by that person.

Also, medical gloves are reversible; therefore a better solution exists, which uses

${\displaystyle \min \left(\lceil M/2\rceil +N,M+\lceil N/2\rceil \right)}$

gloves where the less numerous group are equipped with a glove each, the more numerous in pairs. The first of each pair use a clean interface, the second reverse the glove.