Well, the original problem was X-rated, so let me recast it.

Three surgeons (A, B, C) participate in an operation involving three patients (a, b, c). For simplicity, each surgeon operates with just one hand, and operates just once on each patient. There are a bunch of sterile surgical gloves that stop contamination from one side to the other. What’s the minimum number of gloves needed to ensure that no body part ever comes into contact with another, even indirectly? Note, surgeons do not want to contaminate each other either.

Clearly, the upper bound is 9, for the 9 pairings. The lower bound is 3, for the 3 patients, or alternatively the 3 surgeons. Is the answer something in between?

Here’s a hint, they are allowed to wear multiple gloves or flip them inside out or do any such thing as needed.

It turns out 3 is not sufficient, but 4 is. There are many ways to achieve 4. Here is one:

First label the 4 gloves 1, 2, 3, 4. The notation “X-m-n-y” indicates surgeon X wears glove n outside glove m and operates on patient y.

A-1-3-c
A-1-2-b
A-1-a
B-4-3-c
B-4-2-b
B-4-1-a
C-3-c
C-3-2-b
C-3-1-a

But no matter how you try, 3 is not possible. You are always short by 1 or 2 sterile surfaces, depending on how you count. And this counting argument lies behind the following proof that 3 is not sufficient. The proof is rather short:

First, two facts.

1. Clearly, once a sterile surface is used by a surgeon or patient, it cannot come into contact with somebody else, so each surface is somehow “assigned” to a specific person.
2. After all the operations involving that person is finished, only then can that person’s assigned surface be contaminated

So, suppose 3 were sufficient. Then, there are 6 persons in total, and 6 sterile surfaces initially. That means there can be no sterile-to-used surface contact until all 6 surfaces are assigned, or there would be a shortage.

There are three types of operations, one type involves contaminating sterile surfaces by direct use, let’s call this an “allocation” operation; a second type involves already contaminated surfaces cross-contaminating each other, let’s call this a “contamination” operation; a third type reuses already contaminated surfaces but in a different yet contact-compatible combination, without introducing additional contamination, let’s call this a “reuse” operation.

There can be at most 5 “allocation” operations to allocate the 6 sterile surfaces to the 6 persons. (The first operation necessarily contaiminates 2 sterile surfaces.)

There can be at most 1 “reuse” operation. This is due to a kind of parity constraint. 4 surfaces have to already be allocated, with 2 sterile surfaces left for this operation.

Now there are 9 operations in total, so there are at least 3 more to go. These remaining operations are “contamination” operations. That means any operation involving surgeons or patients associated with any of the contaminating “inside” glove surfaces must not occur again.

Now, without loss of generality, suppose the glove surface assignments are

A-1-a
B-2-b
C-3-c

(It has to be surgeon on one side, patient on the other, because any other way is necessarily more wasteful.) Now note that any 2 operations involves at least 3 distinct people, and simultaneously “disable” the 3 other sides of the gloves (and the associated people) from further operations. Further, for any 3 people, there can be at most 2 operations between them. That means we can only perform 2 “contamination” operations. As an example, the two operations A-1-2-b, A-1-3-c forbids a, B, and C from being in any further operations. That leaves A, b, c, but between them, there are only the two pairs that have already occurred (A-b and A-c).

Since there is 1 of the 9 operations that cannot be performed in safe conditions, that’s a contradiction. Q.E.D.

Now only if this can be generalized to larger numbers of patients and surgeons. One key number series in making bounds is the least number of distinct people that must be involved for \(N\) operations. We know that a full bipartite graph between \(n\) nodes and \(k\) nodes has \(n \times k\) edges, so \(N\) operations will involve at least about \(2\sqrt{N}\) people. The problem is this approximate lower bound grows too slowly and becomes loose for larger numbers of pairings so that doesn’t guarantee as simple a proof for those cases. So maybe another day for the generalization.