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.

More Is Less

So, I find it to be rather unfortunate that the night after posting my puzzle about shaking hands from last time, I managed to come up with a similar problem that I consider to be more interesting. This leaves me with the issue of either solving that puzzle from last time and then posting the new puzzle as a follow-up, or just posting the new puzzle and solving them both at once next time. The problem with the former is that after the first puzzle is solved, the second puzzle is very easy to do (its the exact same logic), but it does have one extra thing one needs to notice in order to solve it, so it still is not trivial. The problem with the latter is that I find it unappealing for aesthetic reasons that don't really make sense.

Going with aesthetics, I guess I might as well solve the puzzle from last time now. The logic is very simple, first of all notice that each person has 2N people available to shake hands with (of the 2N+2 people, they cannot shake their own or their partners), and so the number of hands each person shakes is between 0 and 2N. You asked 2N+1 people how many hands they shook, and you received 2N+1 unique answers, thus you must have received every answer between 0 and 2N, pigenhole principle and all that. We will identify each person by the number of hands they shook, that is, person k shook k hands, and this assignment gives each person a unique number.

Person 2N must have shaken hands with every person they could, and person 0 must have done the opposite. These two people must be partners, or those two people did not go to the same party. Thus, (0,2N) is a pair. Now, each person at the party outside of that pair must have shaken hands with exactly one person in that pair (2N, to be specific), so lets just remove pair (0,2N) and reduce everybodys number by 1. This has now set up the exact same situation as the original problem, but we have reduced N to N-1. Everybody's number is 1 lower, but they are all still unique. This means that whatever the solution is to the problem with N (call that F(N)) it will be 1 lower when N is instead N-1. That is to say

F(N) = F(N-1)+1

Which means

F(N)=F(1)+N-1

so we just have to solve the N=1 case.

When N=1, the answers you were told were 0,1, and 2. 2 and 0 must be partners by the same logic as before, and 1 must be your own partner. Since 2 shook hands with 2 people, the other hand must have been yours, and 0 did not shake your hand. This means that F(1) is 1 and therefore F(N) is N. Proving that you shook hands with N people, exactly 1 person from each couple.

Now for the follow-up puzzle:

You go to a party with 2N other people (so there are 2N+1 people in total at this party). At the party people shake hands with other people. No person shakes hands with themselves. After the party, you ask each person that was at the party how many different people they shook hands with, and each person gives you a unique answer. How many different people did you shake hands with?

Very much the same setup, but the "couples" concept has been stripped away.

Shaking Hands

New puzzle time. Mark told me this one a week or two ago, and since he is approximately 90% of my readership I'm not sure why I'm posting it, but here we go:

You and your partner go to a party with N other couples (so there are 2N+2 people in total at this party). At the party people shake hands with other people. No person shakes hands with themselves or with their partner. After the party, you ask each person that was at the party how many different people they shook hands with, and each person gives you a unique answer. How many different people did you shake hands with?

Mark initially asked me this with N=5, and then found it wasn't more interesting to generalize it to N. I will initially ask it with N and find it isn't any more interesting to specify it to 5.