When Condoms Cost $1000

I try to avoid televised sports so, instead of watching the World Cup match between France and that other country (Poland? Paraguay? Meh, something like that), I'm browsing the operations research category in Wikipedia.

Here's a gem: the safe sex makespan problem.

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

Those dirty OR people and their hot safe-sex orgies. At least I'll never have to worry about this particular problem.