home *** CD-ROM | disk | FTP | other *** search
/ ftp.pasteur.org/FAQ/ / ftp-pasteur-org-FAQ.zip / FAQ / puzzles / archive / induction < prev    next >
Encoding:
Internet Message Format  |  1996-04-26  |  3.7 KB
  1. Received: from MIT.EDU (PACIFIC-CARRIER-ANNEX.MIT.EDU [18.69.0.28]) by bloom-picayune.MIT.EDU (8.6.13/2.3JIK) with SMTP id OAA03553; Sat, 20 Apr 1996 14:53:49 -0400
  2. Received: from [199.164.164.1] by MIT.EDU with SMTP
  3.     id AA15884; Sat, 20 Apr 96 14:13:19 EDT
  4. Received: by questrel.questrel.com (940816.SGI.8.6.9/940406.SGI)
  5.     for news-answers-request@mit.edu id LAA25279; Sat, 20 Apr 1996 11:13:59 -0700
  6. Newsgroups: rec.puzzles,news.answers,rec.answers
  7. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!questrel!chris
  8. From: chris@questrel.questrel.com (Chris Cole)
  9. Subject: rec.puzzles Archive (induction), part 16 of 35
  10. Message-Id: <puzzles/archive/induction_745653851@questrel.com>
  11. Followup-To: rec.puzzles
  12. Summary: This is part of an archive of questions
  13.  and answers that may be of interest to
  14.  puzzle enthusiasts.
  15.  Part 1 contains the index to the archive.
  16.  Read the rec.puzzles FAQ for more information.
  17. Sender: chris@questrel.questrel.com (Chris Cole)
  18. Reply-To: archive-comment@questrel.questrel.com
  19. Organization: Questrel, Inc.
  20. References: <puzzles/archive/Instructions_745653851@questrel.com>
  21. Date: Wed, 18 Aug 1993 06:05:34 GMT
  22. Approved: news-answers-request@MIT.Edu
  23. Expires: Thu, 1 Sep 1994 06:04:11 GMT
  24. Lines: 394
  25. Xref: senator-bedfellow.mit.edu rec.puzzles:24998 news.answers:11518 rec.answers:1918
  26. Apparently-To: news-answers-request@mit.edu
  27.  
  28. Archive-name: puzzles/archive/induction
  29. Last-modified: 17 Aug 1993
  30. Version: 4
  31.  
  32.  
  33. ==> induction/handshake.p <==
  34. A married couple organizes a party. They only invite other married
  35. couples. At least one person of an invited couple is acquainted to
  36. at least the host or the hostess (so between sets {host,hostess} and
  37. {male of invited couple, female of invited couple} there exists at 
  38. least one relation, but two, three or four relations is also possible).
  39. Upon arrival at the party, each person shakes hands with all other
  40. guests he/she doesn't know yet (it is assumed everybody knows 
  41. him/herself and his/her partner). 
  42.  
  43. When all couples have arrived and all the handshaking has been done,
  44. the host mingles between the guests and ask everybody (including his
  45. wife): "How many hands did you shake?". To his surprise, all responses
  46. are different.
  47.  
  48. With the above information, you must be able to determine how many
  49. hands the host and hostess each shook.
  50.  
  51. ==> induction/handshake.s <==
  52. Assume there were 2n people (including host and hostess)
  53. in the party.
  54.  
  55. 1. When the host asked the question he must have got
  56.    2n-1 responses (including from his wife).
  57.  
  58. 2. All of the responses were different.
  59.  
  60. The responses have to be (0, 1, 2, 3, ..., 2n-2)
  61. to satisfy the above requirements. As 2n-2 is the maximum
  62. possible handshakes any person in this party could have made.
  63.  
  64. /**   Below,
  65.       P{x} - means a person who shook x hands.
  66.       H    - means the host
  67.  **/
  68.  
  69. H: <-------->2n-2   0
  70.        2n-3        1
  71.           2n-4          2
  72.       2n-5          3
  73.           .             .
  74.            .           .
  75.              .       .
  76.           n  n-1 n-2
  77.  
  78.         (There are 2n-1 on the circle.)
  79.  
  80. P{2n-2} must have handshaked with H (because in the circle he
  81. can handshake with only 2n-3. He has to exclude himself also.)
  82.  
  83. P{2n-3} must have handshaked with H (because in the circle he
  84. can handshake with only 2n-4.)
  85.  
  86. P{2n-4} must have handshaked with H (because in the circle he
  87. can handshake with only 2n-5.)
  88.  
  89. P{n} must have handshaked with H (because in the circle he
  90. can handshake with only n-1.)
  91.  
  92. from P{n-1} to P{0} nobody  handshakes with H, because, for them
  93. the handshake numbers are satisfied on the circle itself.
  94.  
  95. This leaves H with (n-1) handshakes.
  96. ----------------------------------
  97.  
  98. P{0} must be the spouse of P{2n-2} (since P{2n-2} handshakes with
  99. everbody else.)
  100.  
  101.