home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / sci / math / 17743 < prev    next >
Encoding:
Text File  |  1993-01-06  |  1.6 KB  |  41 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!gatech!usenet.ins.cwru.edu!agate!stanford.edu!nntp.Stanford.EDU!ilan
  3. From: ilan@leland.Stanford.EDU (ilan vardi)
  4. Subject: Re: condoms
  5. Message-ID: <1993Jan6.122524.341@leland.Stanford.EDU>
  6. Sender: news@leland.Stanford.EDU (Mr News)
  7. Organization: DSG, Stanford University, CA 94305, USA
  8. Date: Wed, 6 Jan 93 12:25:24 GMT
  9. Lines: 30
  10.  
  11. I have solved the general problem of the least number of condoms it
  12. takes for m men and n women to have all mxn heterosexual encounters.
  13. The answer is
  14.  
  15.    m = n = 2 => 2 condoms
  16.  
  17.    m = 2k+1, n = 1 => k+1 condoms
  18.  
  19. otherwise, it's the smallest integer greater or equal to m/2 + 2n/3.
  20. I assume that m >= n, otherwise interchange m and n. 
  21.  
  22. The same method solves the problem for m homosexual men all having
  23. sex, and m bisexual men and n heterosexual women (posed by A. Orlitzky
  24. and L. Shepp).
  25.  
  26. The problem was almost solved by Hajnal and Lovasz [``An algorithm to
  27. prevent the propagation of certain diseases at minimum cost,'' in
  28. ``Interfaces between computer science and operations research,''
  29. edited by J.K. Lenstra, A.H.G. Rinnoy Kan, and P. van Emde Boas,
  30. Matematisch Centrum, Amsterdam 1978] who showed that the number was
  31. within 2 of m/2 + 2n/3. In any case, showing that 6 men and 6 women
  32. require only 7 condoms pretty characterizes the algorithm (Hajnal and
  33. Lovasz required 8 condoms).
  34.  
  35. My solution appeard in my book ``Computational Recreations in
  36. Mathematica'', Addison--Wesley, 1991. The reason it appeared there is
  37. that I suspected that interest in this problem might last longer than
  38. interest Mathematica.
  39.  
  40. -ilan 
  41.