Generalization of the two-surgeons-two-patients-and-two-gloves puzzle

Question

^{This is the original puzzle with $n=2$. I recommend solving it before this one to get acquainted with the mechanisms.}

There are $n$ patients in an hospital (let's call them $p_1 \dots p_n$), each of them need an operation of by $n$ different doctors (let's call them $d_1 \dots d_n$) -- so $n^2$ operations in total. However, just before the first operation, it is discovered that there are only $n$ surgeon gloves in the hospital. One single glove is needed for each operation.

Any of the surgeons may be infected with a rare flu, and the patients may be affected as well. The virus that causes the flu transfers readily from flesh to flesh, or from flesh to any object which in turn can contaminate any flesh or object it touches. People avoid touching one another, or touching objects that may be contaminated. In particular, one can catch the flu:

• if they wear a glove that has been previously used by another person.
• if they are touched by (the exterior of) a glove that has been previously used to operate another person.

How can all the operations can be performed using only $n$ gloves and without the risk of anyone catching the flu from one another? For the sake of simplicity ignore the risk of contamination while putting the gloves on the hands of the doctors.

Disclaimer: I don't know the answer. I struggled a bit to find a solution with $n=3$, hoping that the process can be generalized to any $n$ but I failed. For this reason I am not completely sure about what tags to use.

Maybe $n$ gloves are not enough? In this case I'd ask you to find the minimum number $g(n)$ of gloves needed for $n$ patients and $n$ surgeons, but I think that would be a much more difficult puzzle.

Answer 1

Let $n\gt 2$. I can do it by using no more than:

$g(n)\le n+\lfloor \frac{n}{2} \rfloor$

The strategy that establishes this bound is:

1. $d_i,i=1,\dots,\lfloor \frac{n}{2} \rfloor$ operate on $p_j,j=1,\dots,n$ by stacking gloves $(d_i,\emptyset)(\emptyset,p_j)$.

2. Next doctor $d_x$ operates using all gloves of form $(\emptyset,p_j)$, infecting them to $(d_x,p_j)$.

3. Remaining doctors operate using inverted and stacked gloves $(\emptyset,d_i)(d_x,p_j)$.

Notice that step 2. is only needed when $n$ is odd.

If Steve's argument that $g(n)\gt n$ is correct, then $n=3$ is optimally solved with this.

I'm not sure if this is optimal or if we can find a better strategy for $n\gt 3$ ?

---

Below is a deeper analysis of my strategy.

Let $(y,x)$ denote a glove with some inner $y$ and outer $x$ infection pattern.

There is a special step:

0. invert an existing glove $(y,x)$ into $(x,y)$.

Every other step is a new operation $d_i\to p_j$:

1. infects both sides $(d_i, p_j)$ of a new glove $(\emptyset,\emptyset)$.

2. infects a side $(d_i, p_j)$ of an existing glove $(d_i,\emptyset)$ or $(\emptyset,p_j)$.

3. infects one side on one or both stacked gloves $(d_i, x)(y, p_j)$.

4. step 3., but assuming $(x,y)$ exists. (avoids mixing $x$ and $y$.)

Then the original solution ($n=2$) is represented as:

Step 3. (new gloves), then twice step 2., then step 3. (existing gloves).

And my strategy for $n\gt 2$ is represented as:

Step 3. (new gloves), then $n$ times step 2., then steps 0., 3. (existing gloves).

That is, my strategy is somewhat a generalization of the solution to the original puzzle.

P. S. I'm not sure if steps 1. or 4. could ever be useful.

Answer 2

It can be done using

$\left \lceil \frac 5 4 n \right \rceil$ gloves

Outline:

* assing a full complement of $n$ gloves to patients, the rest to a quarter of the doctors
* stacking gloves these doctors can nondestructively treat all patients
* dismiss the doctors who are finished and stack their $\frac n 4$ gloves to yield $\frac n 8$ "clean" gloves
* assign these to new doctors and repeat the last two steps until the doctors' gloves are used up
* at this time about half the doctors will have been dismissed and one glove ("glove X") with one clean side will remain of the doctors' gloves.
* split the patients in two equal groups and assign the gloves of group one to the remaining doctors. One after the other, each doctor can stack their glove with glove X spoiling the patient's side of their glove but preserving the clean side of glove X. Therefore each doctor can nondestructively treat each patient in group two.
* at this time all that's missing are pairings between the remaining doctors and patient group one. We can assign the gloves of patient group two inside out to patient group one and let the doctors finish the job.

Detailed example showing a few rerfinements:

$n=8$ we'll write $A,B,C,...$ for doctors and $1,2,3,...$ for patients, $-$ for clean and $\#$ for spoilt.

We'll need a total of 10 gloves.

start with $(A-) (B-) (-1) (-2) ... (-8)$ and finish all jobs for doctors $A,B$
stack gloves 1 and 2 $(-A:B-)$ and give them to doctor $C$: $(C\#:\#-)$ and finish all jobs for doctor $C$
hand glove 3 to doctor $D$ who, of course, can immediately use them on patient 1 before stacking with glove 2 which will spoil the patient 1 side of glove 3: $(D\#:\#-)$; finish doctor $D$'s schedule
hand glove 4 to doctor $E$: $(E2)$; let them treat patient 2; stack with glove 2 and treat patients 3-8.
current state: gloves: $(C\#) (\#-) (D\#) (E\#) (-3) ... (-8)$ jobs finished: $A,B,C,D,E2-8$
next three steps hand glove 5 (6,7) to doctor $F$ ($G,H$); let them treat patient 3 (4,5) stack with glove 2 and treat patients 4-8 (5-8,6-8)
state now: gloves: $(C\#) (\#-) (D\#) ... (H\#) (-6)(-7) (-8)$ jobs finished: $A-D,E2-8,F3-8,G4-8,H5-8$
hand gloves 8-10 to patients 1-3 $(16) (27) (38)$ and glove 2 to patient 4 $(4\#)$ and let them be treated by doctors E-H as needed.
final state gloves $(C\#) (\#4) (D\#) ... (H\#) (1\#) (2\#) (3\#)$ all jobs done

Answer 3

First, observe that:

the number of sides of gloves is exactly equal to the number of people that must touch at least one side of at least one glove.

as such

by the "pigeonhole principle", with exactly $n$ gloves, each side of each glove must be reserved exclusively for being touched by at most one person before it is irreversibly contaminated.

During the procedures a surface of a glove can be in one of 3 states:

1. "clean" - i.e. Not touched by anyone, and only brought into contact with other "clean" gloves.

2. "used" - i.e. it has been touched at least once by the person two whom it is allocated, and has never been brought into contact with a glove that is not clean.

3. "contaminated" - i.e. it has been touched by someone other than the person to whom it is allocated (not allowed!), or brought into contact with another used glove (allowed, but this glove can now never be touched by anyone).

If it's possible to generalise to $n$, it must necessarily be possible to do 3, so I'll start with that simpler case, where doctors X, Y, Z must all operate on patients A, B, C.

Without loss of generality, X performs the first operation on A. There are two possibilities:

1. A single glove gets touched by X on one side and A on the other. This single glove must then be worn by X for the operations on B and C (with at least one other glove to protect B and C from A), and also must be worn for the operations on A by Y and Z (with other gloves inside to protect Y and Z from X). This glove will contaminate any other glove it touches, so Y and Z must complete both operations on B and C before this glove is used again, leaving non-contaminated used surfaces on both gloves. Unfortunately the known solution for $n = 2$ results in two gloves becoming contaminated on one side, so this does not work, and furthermore, even if that were possible, whichever of "Y operates on A" and "X operates on B" were to happen first would contaminate the other side of the "X/A" glove.

2. X wears two gloves to operate on A, one inside the other. This results in one glove "used by X" on one side, and another "used by A" on one side. In a different variant of this puzzle, where each operation uses two gloves, other doctors can then use these gloves to operate on other patients by turning one of the gloves "used by X" inside out, so the two "used by X" surfaces face each other, without contaminating any other glove. However, in this puzzle, the next person who uses the "doctor X" glove must have another glove outside, which becomes contaminated on that side, so must have been used for all 3 of its operations first, and will thus contaminate the X side of the glove. Therefore X must complete all 3 operations before the other side of that glove is touched. However, a similar argument shows that all 3 operations on A must be completed before the other side of the A glove is touched. That only leaves 1 glove, which is not sufficient to allow X to complete 2 more operations AND for 2 more operations to be performed on A without at least one side of at least one glove becoming contaminated - the remaining glove must be touched by at least one doctor (performing the second operation on A) and at least one patient (for the second operation by X) both whilst the other side is "clean". Contradiction.

It is thus clear that

$n$ gloves are not sufficient, and at least $n+1$ gloves are necessary.

My initial intuition was that

$n+1$ gloves are sufficient, with the additional glove having one side kept "clean" at all times.

So I attempted to come up with

a procedure to allow 3 doctors X Y Z to operate on 3 patients A B C using 4 gloves, in a manner that would generalise to $n$ doctors using $n+1$ gloves.

The first part was relatively easy - e.g.

X and Y uses gloves 1 and 2 respectively to operate on all patients except A (with an allocated glove for each patient) keeping the outside of their glove clean and the inside of the other patient's glove clean, then Z operates on C and B using those gloves, and X and Y operate on A using the glove that's still clean on the outside, and finally Z operates on A, re-using any pair of gloves that were "used by Z" and "used on A" (with the "used on B/C" side of one glove touching the "used by X/Y" side of the other).

For the second part,

I tried various ideas, such as having X's glove turned inside out and placed inside Y's glove after Y had operated on A, so that a "clean surface to A" interface is available, but either got confused, or ended up with procedures that wouldn't extend past 3.

Thus it seems that

my known procedure so far generalises to $2n-2$ rather than $n+1$... i.e. 2 gloves for n=2, 4 for n=3, 6 for n=4, etc.

This remains a "partial answer" while I

further check for ideas that might apply for the case $n=4$ to see if this upper bound can be improved upon, or find some insight towards a proof that $2n-2$ is always needed.

In particular,

The $2n-2$ solution only results in two sides of gloves becoming "contaminated", and my intuition is that an optimal solution could contaminate anything up to both sides of all gloves except the ones used in the final operation - giving plenty of scope for further improvements.

A later refinement of that intuition while I was considering improvements to @vepir's answer which I never got completely nailed down was that

there is never any need to contaminate the second side of any glove, as the operation that contaminates the second side would need at least two other gloves, and could equally occur without that glove used at all (allowing the contaminated surfaces of the inner and outer gloves to touch directly), so an optimal solution would end with all gloves contaminated on exactly one side. This is precisely what @loopywalt's answer does, using a method I'd started to investigate, but not followed to its conclusion, so I've got good reason to believe that one optimal.

Answer 4

Turns out that the optimal solution has been known since 1991. The answer is we need $$\left\lceil\frac{7n}{6}\right\rceil$$ gloves to have $n$ doctors operating on $n$ patients without the risk of infecting each other. This number is optimal.

Ilan Vardi published it in chapter 10 of Computational Recreations in Mathematica (Addison-Wesley). Both the proof of optimality and the algorithm for achieving it are complex, but the main points are summarized below.

Partial Upper-bound

We prove the upper-bound for $n=2k$ and $m=3l$ ($m\geq n$) by giving an algorithm that works for $n$ doctors, $m$ patients using $\frac{n}{2}+\frac{2m}{3}+1$ gloves (which is equal to $\left\lceil\frac{7n}{6}\right\rceil$ for $n=m\neq 6k$ for some $k$).

As in the question, denote the patients as $p_i$, doctors as $d_i$, and gloves as $g_i$.

1. $d_{2i-1}$ use $g_i$ for $i=1,\ldots,k$, $p_{3j-2}$ use $g'_{2j-1}$, and $p_{3j-1}$ use $g'_{2j}$ for $j=1,\ldots,l$. That's $k+2j$ gloves so far, and an extra glove $G$ will be used to protect $g'_i$.
2. Have the operations using $d_{2i-1}-\overrightarrow{g_i}-\overrightarrow{g'_{2j-1}}-p_{3j-2}$ and $d_{2i-1}-\overrightarrow{g_i}-\overrightarrow{g'_{2j}}-p_{3j-1}$.
3. Turn $g'_{2j}$ inside out to be used by $p_{3j}$.
4. Have the operations using $d_{2i-1}-\overrightarrow{g_i}-\overrightarrow{G}-\overleftarrow{g'_{2j}}-p_{3j}$.
5. Doctors $d_{2i-1}$ are now done. Turn their gloves $g_i$ inside out to be used by $d_{2i}$.
6. Have the operations using $d_{2i}-\overleftarrow{g_i}-\overleftarrow{G}-\overrightarrow{g'_{2j-1}}-p_{3j-2}$ and $d_{2i}-\overleftarrow{g_i}-\overleftarrow{g'_{2j}}-p_{3j}$.
7. Patients $p_{3j-2}$ are now done. Turn their gloves $g'_{2j-1}$ inside out to be used by $p_{3j-1}$.
8. Have the operations using $d_{2i}-\overleftarrow{g_i}-\overleftarrow{g'_{2j-1}}-p_{3j-1}$.
9. We are done.

Partial Lower-bound

1. Make a graph with $n+m$ vertices, representing the doctors and patients. The gloves will be the edges.
2. An edge will be formed between two vertices representing the gloves' sides infected by the corresponding doctor or patient. The direction of the edge depends on which side gets infected first. The side which gets infected first is the source of the edge, and the side which gets infected later is the target of the edge. If infection occurs simultaneously, take arbitrary direction.

For example, the 2 doctors 2 patient solution is the graph $d_1 \rightarrow p_1\ \ \ d_2 \rightarrow p_2$.

The partial upper-bound algorithm above has the graph in the form of $\overbrace{d\rightarrow d}^{\frac{n}{2}\text{ times}}\ \ \ \overbrace{p\rightarrow p \rightarrow p}^{\frac{2n}{3}\text{ times}}$.

Now, the most efficient use of a glove is to use one side for one person, and the other side for another person, for all operations. This gives one glove for two persons. We want to maximize this use as much as possible. The second type, which is the next most efficient use is for three persons to use two gloves.

Note that for the 2-person setup to work, one person must finish all operations first with that glove, and only then give it to the second person. This implies that 2-person setup cannot occur on both the doctors side and the patients side. Another observation is that there can be at most one 2-person setup for doctor-patient and one 2-person setup for patient-doctor.

By these observations and the fact that no vertex can be isolated, the optimal solution must be in the form of $d \rightarrow p\ \ \ d\leftarrow p\ \ \ \overbrace{d\rightarrow d}^{\frac{n-2}{2}\text{ times}}\ \ \ \overbrace{p\rightarrow \ldots \rightarrow p}^{\text{rest of the patients}}$, with the "rest of the patients" part cannot contain 2-person setup.

This means that at least there has to be $\frac{n-2}{2}+2+\frac{2}{3}(m-2) = \frac{n}{2}+\frac{2m}{3}-\frac{1}{3}$ gloves. Note that this gives $7n$ gloves for $n$ multiples of 6, whereas the partial upper-bound above gives $7n+1$.

Rest of the proof

The rest of the proof from the book generalizes the above upper-bound and lower-bound for arbitrary $n,m$ (and not just $n=2k, m=3l$), also resolves the discrepancy between the upper-bound and the lower-bound for $n,m$ multiples of 6, finally concluding that $\displaystyle\left\lceil\frac{n}{2}+\frac{2m}{3}\right\rceil$ is the optimal number of gloves required for $n$ doctors and $m$ patients.

For this question, since $n=m$, we have the optimal number of gloves is $\displaystyle\left\lceil\frac{7n}{6}\right\rceil$.