Alice and Bill threw a party and invited four other couples. As each couple arrived there were greetings, including handshakes.

Later in the evening, Bill asked everyone, including Alice how many people they shook hand with. Every answer was different. No one shook hands with his or her own partner.

How many hands did Alice shake?

This is a very clever problem.

However, I've found that it's possible to solve it by assuming that there is a unique solution, much like in "Tricky Area."

If we assume there is a unique solution, exactly one answer between 0 and 8 should work.  Given any pair of the ten guests that is not a couple, they either shook hands or they didn't, 1 or 0.  For any working solution, we can invert all the hand-shaking between 1 and 0 to achieve another solution.  The number of hands each person shook will change from N to 8-N.

So if the unique solution is that Alice shook X hands, there exists another solution where she shakes 8-X hands.  This is a contradiction unless X=8-X.  Therefore Alice shook 4 hands.

Posted by Tristan on 2005-07-02 23:55:05