Archive-name: puzzles/archive/induction
Last-modified: 17 Aug 1993 Version: 4 See reader questions & answers on this topic! - Help others by sharing your knowledge ==> induction/handshake.p <== A married couple organizes a party. They only invite other married couples. At least one person of an invited couple is acquainted to at least the host or the hostess (so between sets {host,hostess} and {male of invited couple, female of invited couple} there exists at least one relation, but two, three or four relations is also possible). Upon arrival at the party, each person shakes hands with all other guests he/she doesn't know yet (it is assumed everybody knows him/herself and his/her partner). When all couples have arrived and all the handshaking has been done, the host mingles between the guests and ask everybody (including his wife): "How many hands did you shake?". To his surprise, all responses are different. With the above information, you must be able to determine how many hands the host and hostess each shook. ==> induction/handshake.s <== Assume there were 2n people (including host and hostess) in the party. 1. When the host asked the question he must have got 2n-1 responses (including from his wife). 2. All of the responses were different. The responses have to be (0, 1, 2, 3, ..., 2n-2) to satisfy the above requirements. As 2n-2 is the maximum possible handshakes any person in this party could have made. /** Below, P{x} - means a person who shook x hands. H - means the host **/ H: <-------->2n-2 0 2n-3 1 2n-4 2 2n-5 3 . . . . . . n n-1 n-2 (There are 2n-1 on the circle.) P{2n-2} must have handshaked with H (because in the circle he can handshake with only 2n-3. He has to exclude himself also.) P{2n-3} must have handshaked with H (because in the circle he can handshake with only 2n-4.) P{2n-4} must have handshaked with H (because in the circle he can handshake with only 2n-5.) P{n} must have handshaked with H (because in the circle he can handshake with only n-1.) from P{n-1} to P{0} nobody handshakes with H, because, for them the handshake numbers are satisfied on the circle itself. This leaves H with (n-1) handshakes. ---------------------------------- P{0} must be the spouse of P{2n-2} (since P{2n-2} handshakes with everbody else.) User Contributions:
[ Usenet FAQs | Web FAQs | Documents | RFC Index ]
Send corrections/additions to the FAQ Maintainer: archive-comment@questrel.questrel.com
Last Update March 27 2014 @ 02:12 PM
|
Comment about this article, ask questions, or add new information about this topic: