6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This can be generalized to undirected connected graphs. If some useful information appears there, it might help proving the (so far best) result by loopy walt as the optimal solution. $\endgroup$
    – Vepir
    Jun 3 at 17:50
  • $\begingroup$ I was once asked a version of this puzzle but it was a bit more NSFW and involved other latex products that are not gloves, and it wasn't the flu they were afraid of ;) $\endgroup$ Aug 17 at 14:36
  • $\begingroup$ @ExtraFishness yeah, it's the so called "vulgar version" mentioned in the original puzzle with $n=2$: puzzling.stackexchange.com/questions/109752/… $\endgroup$
    – melfnt
    Aug 28 at 8:29
4
$\begingroup$

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:

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

$\endgroup$
1
  • $\begingroup$ Step 1 is useful for n=1. $\endgroup$
    – Florian F
    May 19 at 21:25
4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ I.e. done using rot13{ a cyhf prvy((a cyhf gjb) bire sbhe) } gloves. $\endgroup$
    – Vepir
    May 26 at 11:23
  • 1
    $\begingroup$ @Vepir I've updated with the precise number. See detailed example for how to achieve it. $\endgroup$
    – loopy walt
    May 26 at 13:11
  • $\begingroup$ I have thought about this, and it seems this might be optimal, but I'm still not sure how to prove it. $\endgroup$
    – Vepir
    Jun 4 at 0:25
  • $\begingroup$ This is good. There are a few details that are not clear in the outline and that you refine in the example, such as: after the first part the number of dismissed doctors is actually less than n/2. How does the other complete their schedule, to begin the next phase with n/2 doctors? (the "remaining doctors" as you call them in your answer). Maybe you want to clarify these details? $\endgroup$
    – melfnt
    Jun 4 at 12:03
  • $\begingroup$ All the information is there. I chose to organise it into outline (big picture, we don't care whether it is exactly half the doctors or maybe one or two fewer) and (boring) micro optimisation conveyed by example. Some may like it that way some may prefer other ways of presentation. It's matter of taste. $\endgroup$
    – loopy walt
    Jun 10 at 21:36
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ We can improve the O(2n) to O(1.5n) - see my answer. I'm not sure if this can be improved further or not. $\endgroup$
    – Vepir
    May 19 at 18:44
  • $\begingroup$ @Vepir $O(2n)$ and $O(1.5n)$ are literally the same thing ... see big O notation. What you want to say is probably $2n + O(1)$ vs $1.5n + O(1)$. $\endgroup$
    – WhatsUp
    May 30 at 16:54
  • $\begingroup$ @WhatsUp It's the same by that definition, but sometimes, $O(c\cdot n)$ is used to put emphasis on the constant (source: my numerical methods professor that may or may not like to abuse notation). $\endgroup$
    – Vepir
    May 30 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.