S'ils sont réutilisables et que je ne dis pas n'importe quoi :

> Question préliminaire : montrer que n² préservatifs suffisent.

Il y a n² relations, donc ça me parait assez trivial d'en déduire que n² préservatifs suffisent

> Question préliminaire (oui, ça prend tout son sens ici) : montrer que 2n préservatifs suffisent.

Il y a 2n participants et on peut "empiler les préservatifs", ça me parait là encore trivial : tout le monde a son préservatif et ils ne sont pas contaminés.
En gros tant qu'on reste dans la catégorie a/b c/d et que les faces b et c ne sont jamais contaminées, on peut garder son préservatif

> Vraie question : De combien de préservatifs a-t-on besoin au maximum ?

Il doit y avoir moyen d'optimiser ça. Déjà 2n-1 est faisable (on utilise un seul préservatif au lieu de 2 sur le premier rapport)
Et par récurrence je peux trouver 2n-2 (pour 2 on a besoin de 2 seulement, et à chaque fois qu'on ajoute 2 participants (soit n+1) on a juste besoin de 2 préservatifs en plus - un par participant)
Idéalement en forçant un peu la réflexion on doit pouvoir obtenir quelque chose comme n ou n+1 mais je vois pas comment.

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.

2499 ? (J'ai du me planter quelque part dans mon raisonnement ceci dit, ou en comptant)

Intuitivement :

Chaque multiple de 5, chaque multiple de 5², chaque multiple de 5^3, chaque multiple de 5^4, chaque multiple de 5^5