Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!utgpu!utcsri!arvind From: arvind@utcsri.UUCP Newsgroups: ut.theory Subject: THEORY NET: Sanitary surgeons and safe sex Message-ID: <5681@utcsri.UUCP> Date: Wed, 18-Nov-87 15:26:46 EST Article-I.D.: utcsri.5681 Posted: Wed Nov 18 15:26:46 1987 Date-Received: Fri, 20-Nov-87 22:31:09 EST Distribution: ut Organization: CSRI, University of Toronto Lines: 44 Date: 16 Nov 1987 10:17:55-EST (Monday) From: "Gregory J. E. Rawlins" 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