Safe sex makespan

The safe sex makespan problem is used in operations research as an example that the cheapest capital cost often leads to dramatic increase in operational time, but that the shortest operational time need not be given by the most expensive capital cost.

M men are each to have safe sex with N women using condoms. Each condom can be used any number of times, but the same side of one condom cannot be exposed to more than one person. Condoms can be re-used any number of times, and more than one can be used simultaneously.

Given M men and N women, the minimum number of condoms C(M ,N) required for all the men to have safe sex with all the women is given by:

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

Details

A naive approach would be to estimate the number of condoms as simply C(M, N) = MN. But this number can be significantly reduced by exploiting the fact that each condom 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 condom, 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 men's condoms meets only the inner surface of the women's condoms. This gives an answer of M + N condoms, 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 condoms were used. Clearly in this case, increasing capital cost has not produced a shorter operation time.

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

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

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

The makespan is then given by:

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

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

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

One or the other solution may be preferred depending on the relative cost of a condom 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.

Other factors

In practical terms using more than one condom at a time is unsafe, as the friction between the condoms makes breakage more likely. Also, safe sex practice usually recommends reducing the number of partners, as opposed to the large number of pairings in the example.

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

Also condoms are reversible, therefore a better solution exists which uses

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

condoms where the less numerous sex are equipped with a condom each, the more numerous in pairs. The first of each pair use a clean interface, the second reverse the condom.

References

• Vardi, I. The Condom Problem. Ch. 10 in Computational Recreations in Mathematica. Redwood City, CA: Addison–Wesley, pp. 203–222, 1991.