arvind@utcsri.UUCP (11/18/87)
Date: 16 Nov 1987 10:17:55-EST (Monday) From: "Gregory J. E. Rawlins" <IUVAX!RAWLINS@rutgers.edu> Subject: Sanitary surgeons and safe sex. In article <18874@yale-celray.yale.UUCP> shefter@yale-zoo-suned.UUCP (Bret A. Shefter) writes: >Three doctors are going to operate on a seriously ill patient. Dr. Stevens >points out that each of the three doctors will need to operate, one after the >other, in his or her special area to save the patient's life, and there can be >no pauses. Dr. Rimaldi mentions that, as there is a strange disease going about >that can be spread by touch, and none of them knows whether his or her fellow >doctors has it (or even if the patient does), since the symptoms do not mani- >fest for three weeks, they had all better use different gloves, even though >they will not be operating together. Dr. Watson (sorry!) discovers that, alas, >there are only two clean pairs of rubber gloves. What to do, what to do? [To rec.puzzle readers: this posting is not a spoiler for this puzzle.] This is the sanitary surgeons puzzle first proposed, to the best of my knowledge, in Martin Gardner's _Aha! Insight_ (Freeman, 1978). I first saw (a generalization of) this puzzle in a graduate class in complexity theory at Waterloo several years ago. The generalization -- first proposed (again, to the best of my knowledge) at either STOC or FOCS circa 1979 -- has since gained notoriety in the complexity theory underground. The reason being that it was posed as the following safe sex puzzle: Given n heterosexual couples, each person wants to have sex with every person of the opposite sex. However, everyone is afraid of transmitting or receiving a communicable disease. They decide that condoms give best protection. What is the minimum number of condoms necessary? Hint: show that for n=2, two condoms are necessary and sufficient. Have fun! gregory. P.S. The solution is know (but not published anywhere!). I would be interested in hearing from anyone who has more detail on either the history of this problem or its further generalization to n males and m females. This problem is more usually stated as a problem in optimization research. -- Gregory J. E. Rawlins; Dept CS, Indiana University, rawlins@iuvax.cs.indiana.edu