Solution: How Many Hands Did She Shake?

David Cowan, a venture capitalist, put a logic puzzle up on his blog. Unable to resist a puzzle, I sat down and tried to come up with a solution. He uses the puzzle to test potential VC's during interviews. I guess I would have failed the interview since it took me almost an hour to come up with the solution.

(don't read any farther if you want to solve it yourself).

Ok here's my solution

  1. There are 10 individuals in the puzzle
  2. There are only 8 people in each persons "set" of possible handshakes
  3. There must be 9 unique answers (the asker doesn't count), therefore the answers must be 0-8 (9 unique answers), this also means if there must be a repetition it's the asker and his wife.
  4. If one person (lets call them A) must shake 8 hands, then for there to be a 0 answer it must be A's partner, B, (since the only person outside A's "set" list is their partner, and they must use everyone in their set to get 8) The score is:
    • A=8
    • B=0
    • Everyone else = 1
  5. Since the 8 and 0 answers must be unique (no one else can now shake hands with them), the 8-0 pair "exits" the puzzle, their "set" is removed limiting each subsequent pair's possible handshake partners to total set-2=6.
  6. For their to be a 7 answer, C, must now shake hands with everyone in their "set" (now 6). For there to be a 1 answer, it must be C's partner, D (who already shook with A), the only person outside C's set. Now the score is
    • A=8
    • B=0
    • C=7 (1 from shaking with A + 6 remaining set)
    • D=1 (from shaking with A)
    • Everyone else 2 (1 from shaking with A, 1 from shaking with C)
  7. Again, 7 and 1 are unique so that pair is removed reducing the available hand shake set, set-2=4.
  8. Repeating those steps, each pair must represent the answers 8-0, 7-1, 6-2, 5-3 leaving the wife to have the number "4" along with the asker.

I drew several diagrams to help come up with this logic, this is what they look like.