Alone At The Party

Time for the solution of the follow up to the shaking hands problem.

I came up with the puzzle itself upon realizing that the people in the initial problem naturally pair up. If one person shook everybodys hand and one person shook nobodys hand, those two people are naturally partners, and everybody shook exactly one hand of that partnership.

To see how this puzzle solves out, lets consider a simpler case. With N=1, there are 3 people at the party, including yourself. You asked the other two people how many hands they shook, and they each gave you a different answer. The possible answers are in the set {0,1,2}, so you must have heard the answers {0,1}, {0,2}, or {1,2}. It is easy to see that {0,2} is impossible, since 2 shakes hands with everybody and 0 shakes hands with nobody, they couldn't have both gone to the same party. In the case {0,1} it must have been you who shook hands with the 1, since it wasn't the 0 who did, thus, you shook one hand. In the case {2,1} 2 must have shaken hands with 1 and with yourself, and so again, you shook hands with exactly 1 person. Therefore we see that for N=1, the answer to the puzzle is 1.

One can arrive at this answer much faster by simply seeing that the two other people shook hands with a different total number of people, thus exactly one of them must have shaken hands with you. You don't know if they shook hands with eachother, and don't care, you get the answer of 1.

Now, generalizing to N, the 2N people we asked must have given answers from the set {0,1,2,...2N}, and so exactly one of those must not have appeared. There is no way both 0 and 2N appeared though, so the answers were either {0,1,2,...2N-1} or {1,2,3,...2N}. In the former case, 0 shook hands with nobody, and 2N-1 shook hands with everybody but 0, so lets remove that pair and reduce everybodys number by 1, after which the answers we have heard are {0,1,2,...2N-3}. N has been reduces by exactly 1 and the total answer has also, so if F(N) is the answer we seek, F(N)=F(N-1)+1. In the other case {1,2,3,...2N}, 2N shook hands with everybody, and 1 only shook hands with 2N, so lets remove that pair and reduce everybodys number by 1 again, after which the answers we have heard are {1,2,3,...2N-2} again we see that F(N)=F(N-1)+1. Since F(1)=1, we can see that F(N)=N again, just like the last puzzle.

Note that if there are an even total number of people at the party, the puzzle cannot be solved. The same reduction down to a simpler case still holds, but when you get down to yourself and 1 other person, you have no way to know if you shook hands with that other person or not. Basically, the two cases split the puzzle into whether or not partners shook hands. When you are a member of a partnership you need some additional information on the puzzle to finish things off, but if you are the odd man out, then you do not care if partners shake hands with eachother.