3 ms·

Similar reasoning solves one of my favorite brain teasers: “My wife and I greet 4 other couples. After the handshakes, I ask everyone how many people they shoo

by todd8 8y ago

Similar reasoning solves one of my favorite brain teasers: “My wife and I greet 4 other couples. After the handshakes, I ask everyone how many people they shook hands with and get no duplicate replies; no one shook hands with their partner or themselves. How many people did my wife shake hands with?” This puzzle stumps everyone I know that hasn’t been exposed to combinatorics.

ahelwer 8y ago
Fun! Let's see; there are 10 people, and 5 couples. Since nobody shook hands with themselves or their partner, everyone (except the question asker, critically) maps to a unique shake number in the set 0 .. 8 (cardinality 9). The question asker also shook one of 0 .. 8 hands, same as one of the other people (otherwise there would be no solution per pigeon-hole principle). We can easily see the 8-hand-shaker must have a 0-hand-shaker as their partner (since everyone else shook at least one hand, the all-shaker's). We can also see, when constructing possible graphs for smaller total numbers of couples (1, 2, 3, 4, etc.) that if the shake graph of N couples satisfies the uniqueness constraint then we can always add another couple in a way which preserves uniqueness: the new couple is an (2N-2, 0) shaker pair, where everyone else has their shake count incremented by one. Thus we see the question-asker's wife's shake-count is equal to the number of other couples, in this case 4. I would still need to prove that any shake-graph satisfying the uniqueness constraint must be unique (under isomorphism swapping shake numbers within couples); we saw with the iterative construction that the answer is equal to the number of other couples, but it isn't yet clear that this is the only possible answer. Of course, we can infer from the question itself that there is a unique solution, and so any found solution must therefore be unique :P
- waterhouse 8y ago
  After the "8 must be paired with 0" step, my next step was to say, "Now, there is someone who shook hands with 7 people. We know he didn't shake hands with Mr. 0, so he must have shaken hands with everyone else except his wife. Meanwhile, there's also someone who shook hands with 1 person, and we already know he shook with Mrs. 8, so he must have not shaken hands with anyone else. Therefore, 7 and 1 must be a couple." Then, accounting for the shakings with 7 and 8 and the non-shakings with 0 and 1, we similarly see that 2 can't have shaken hands with anyone else, but 6 must have shaken hands with everyone else except his partner, so 2 and 6 must be paired as well. The 5-3 pairing follows too, after which we're left with 4 and the question-asker, who are a couple by process of elimination. Incidentally, we conclude that the question-asker also shook hands with 4 people: Mrs. 8, 7, 6, and 5.

by todd8 8y ago

ahelwer 8y ago

Fun! Let's see; there are 10 people, and 5 couples. Since nobody shook hands with themselves or their partner, everyone (except the question asker, critically) maps to a unique shake number in the set 0 .. 8 (cardinality 9). The question asker also shook one of 0 .. 8 hands, same as one of the other people (otherwise there would be no solution per pigeon-hole principle). We can easily see the 8-hand-shaker must have a 0-hand-shaker as their partner (since everyone else shook at least one hand, the all-shaker's). We can also see, when constructing possible graphs for smaller total numbers of couples (1, 2, 3, 4, etc.) that if the shake graph of N couples satisfies the uniqueness constraint then we can always add another couple in a way which preserves uniqueness: the new couple is an (2N-2, 0) shaker pair, where everyone else has their shake count incremented by one. Thus we see the question-asker's wife's shake-count is equal to the number of other couples, in this case 4. I would still need to prove that any shake-graph satisfying the uniqueness constraint must be unique (under isomorphism swapping shake numbers within couples); we saw with the iterative construction that the answer is equal to the number of other couples, but it isn't yet clear that this is the only possible answer. Of course, we can infer from the question itself that there is a unique solution, and so any found solution must therefore be unique :P

waterhouse 8y ago
After the "8 must be paired with 0" step, my next step was to say, "Now, there is someone who shook hands with 7 people. We know he didn't shake hands with Mr. 0, so he must have shaken hands with everyone else except his wife. Meanwhile, there's also someone who shook hands with 1 person, and we already know he shook with Mrs. 8, so he must have not shaken hands with anyone else. Therefore, 7 and 1 must be a couple." Then, accounting for the shakings with 7 and 8 and the non-shakings with 0 and 1, we similarly see that 2 can't have shaken hands with anyone else, but 6 must have shaken hands with everyone else except his partner, so 2 and 6 must be paired as well. The 5-3 pairing follows too, after which we're left with 4 and the question-asker, who are a couple by process of elimination. Incidentally, we conclude that the question-asker also shook hands with 4 people: Mrs. 8, 7, 6, and 5.