A host and his spouse invite four other couples. People shake hands with some of the others, nobody shakes their own spouse and nobody shakes themselves. The host asks the other nine people how many hands they shook and receives nine different answers. How many hands did the host's spouse shake?

A host and his spouse invite four other couples. People shake hands with some of the others, nobody shakes their own spouse and nobody shakes themselves. The host asks the other nine people how many hands they shook and receives nine different answers. How many hands did the host's spouse shake?

Approach: The nine answers must fill a fixed range with no repeats. Identify who the extreme answers have to be married to, remove that couple, and repeat on what remains.

4. Each of the nine can shake at most 8 hands, so nine distinct answers must be exactly 0, 1, 2 up to 8. The person answering 8 shook everyone except himself and his spouse, and the person answering 0 shook nobody, so those two are married, since otherwise the 8 would have shaken the 0. Remove that couple and drop every remaining count by 1, because each of the others shook the 8. Seven people remain with distinct counts 0 through 6, and the same step marries 7 to 1, then 6 to 2, then 5 to 3. Those four pairs are the four guest couples, so the only person not accounted for is the host's spouse, whose count is 4. The same induction shows the host also shook 4 hands.

Follow-up: With n guest couples instead of four, what does the host's spouse answer, and what is the host's own count?

Key concepts: pigeonhole on distinct counts, pairs of spouses, induction by removal.