Editing Glove problem (section)

==Details==
A naive approach would be to estimate the number of gloves as simply ''G''(''M'',&nbsp;''N'') =&nbsp;''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''&nbsp;+&nbsp;''N'' gloves, which is significantly lower than&nbsp;''MN''.

The [[makespan]] with this scheme is ''K''&nbsp;·&nbsp;max(''M'',&nbsp;''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'',&nbsp;''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''&nbsp;&minus;&nbsp;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 #&nbsp;1's glove, so it's still safe.

This scheme uses (1&nbsp;·&nbsp;''N'')&nbsp;+&nbsp;((''M''&nbsp;&minus;&nbsp;1&nbsp;&minus;&nbsp;1)&nbsp;·&nbsp;1) + (1&nbsp;·&nbsp;0) =&nbsp;''M''&nbsp;+&nbsp;''N''&nbsp;&minus;&nbsp;2 gloves. This number cannot be reduced further.

The makespan is then given by:
* ''N'' serial interactions to plant the gloves.
* max(''M''&nbsp;&minus;&nbsp;2,&nbsp;''N'') parallelized interactions for intermediate stage.
* ''N'' serial interactions to collect the gloves.

Makespan: ''K''&nbsp;·&nbsp;(2''N''&nbsp;+&nbsp;max(''M''&nbsp;&minus;&nbsp;2,&nbsp;''N'')).

Clearly, the minimum ''G''(''M'', ''N'') increases the makespan significantly, sometimes by a factor of&nbsp;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''&nbsp;+&nbsp;''N''&nbsp;&minus;&nbsp;1) should also occur as a candidate solution, but this requires such narrow windows on ''M'',&nbsp;''N'' and the cost parameters to be optimal that it is often ignored.