==> 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.) . . . same logic till P{n-2} leaving the Hostess to be P{n-1}. ---------------------------------------- So, Host - made (n-1) handshakes. Hostess - made (n-1) handshakes. where n is the number of couple including the host couple. ----------------------------------------