Article: 19848 of sci.math
Newsgroups: sci.math
From: ilan@leland.Stanford.EDU (ilan vardi)
Subject: Re: condoms
Message-ID: <1993Jan6.122524.341@leland.Stanford.EDU>
Sender: news@leland.Stanford.EDU (Mr News)
Organization: DSG, Stanford University, CA 94305, USA
Date: Wed, 6 Jan 93 12:25:24 GMT
Lines: 30

I have solved the general problem of the least number of condoms it
takes for m men and n women to have all mxn heterosexual encounters.
The answer is

   m = n = 2 => 2 condoms

   m = 2k+1, n = 1 => k+1 condoms

otherwise, it's the smallest integer greater or equal to m/2 + 2n/3.
I assume that m >= n, otherwise interchange m and n. 

The same method solves the problem for m homosexual men all having
sex, and m bisexual men and n heterosexual women (posed by A. Orlitzky
and L. Shepp).

The problem was almost solved by Hajnal and Lovasz [``An algorithm to
prevent the propagation of certain diseases at minimum cost,'' in
``Interfaces between computer science and operations research,''
edited by J.K. Lenstra, A.H.G. Rinnoy Kan, and P. van Emde Boas,
Matematisch Centrum, Amsterdam 1978] who showed that the number was
within 2 of m/2 + 2n/3. In any case, showing that 6 men and 6 women
require only 7 condoms pretty characterizes the algorithm (Hajnal and
Lovasz required 8 condoms).

My solution appeard in my book ``Computational Recreations in
Mathematica'', Addison--Wesley, 1991. The reason it appeared there is
that I suspected that interest in this problem might last longer than
interest Mathematica.

-ilan