n² suffisent : n² relations sexuelles donc évident. 2n suffisent : à chacun son préservatif, et il n'y a pas de contamination possible.
n suffisent en fait :
A chaque mec son préservatif. Chaque fille couche avec un mec différent. Notons IJ le préservatif qui a été utilisé par l'homme I et la fille J. J=f(I) est une bijection de [1,n] Si l'homme A veut coucher avec la fille B, il met le préservatif Af(A) puis par-dessus le préservatif (f^(-1)(B))B. (Ce qui donne en gros un préservatif global AB). Ainsi, aucun des deux ne sera contaminé. Ceci étant vrai pour tout A et B, toutes les relations sexuelles peuvent avoir lieues.
(n-1) ne suffisent pas : les mecs peuvent avoir des MST différentes donc 2 hommes ne peuvent enfiler un préservatif différent.
Donc il faut au moins n préservatifs, et n préservatifs suffisent.