/prog/ homeworkd 5024: The Condom Problem

A well known puzzle among combinatorialists is the following: m men
and n women, each with a different sexually transmitted disease, want
to engage in all mn sexual encounters with no one catching anyone
else's disease and with the minimal number of condoms being used.
You are allowed to nest condoms and to turn them inside out, but
once a surface becomes infected by a disease it stays infected for all
time.

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).

how many diseases do you think ilan vardi caught before he figured it out?