Why Do Handshake Numbers at a Party Always Pair Highest with Lowest?

[Greg825]

I've come up with a partial solution (a correct answer in fact) to this puzzle but am not completely satisfied in that I don't fully see how it works. the problem is:

I and my wife invite 10 couples to a party. At the end I ask everyone except for myself how many people they have shaken hands with and everyone has shaken hands with a different number of people. Partners in a couple can't shake hands with their partner.

What I've gotten so far:
It's apparent that there are 2*m-1 possible numbers of hand shaking where m is the number of pairs because the range is from 0 to n-2 where n is the number of people present. This considered, "I" have to have shaken hands the same amount of times as 1 other person.

After diagramming the situation for small numbers of groups such as 2 3 and 4 it becomes apparent that the largest possible number of handshakes has to be paired with the smallest. Because we have one repeat this leads to the conclusion that both "I" and my wife have to have shaken the median number of hands. To illustrate this try it for groups of 2, 3, and 4 by drawing n dots for n people and choosing one arbitrary person from which you draw n-2 lines to all other dots (the exclusion of 2 is because you can't shake hands with yourself nor your partner). Then move to a second arbitrary couple and draw n-3 lines to the dots that you can without violating the initial conditions of the problem. Continue until you're done. You should find that the median number of handshakes is always paired, and thus
both "I" and my wife have to be that amount.

What I'm still not sure of is exactly why all highest and lowest numbers of handshakes have to be coupled. I do see why this is the case for the extremes though. If we choose an arbitrary couple and assume that person "A" shakes hands with everyone except himself and his partner, only his partner has shaken hands with 0 people now. If we move to a second arbitrary couple and say that person "A" in that couple shakes hands with everyone except the 0-shake person from the previous couple and his partner, we are left with a couple with n-1 and 0+1 shakes where n is the maximum possible number of shakes. I suppose through induction it is apparent that this will continue until we reach a median, which must be paired. Now that I think about it, this may actually be a sufficient proof.


Anyway the actual answer if we assume I am correct is 10 shakes, and the answer will always be equal the the number of couples invited.

Your thoughts?

 

[AKG]

If there are 2n people, then each person shakes anywhere from 0 to 2n-2 people's hands, since he can possibly shake everyone's hand but his own and his partners. When you ask everyone but yourself (that is, 2n-1 people) how many hands they've shook, and they all give different answers, then noting that |{0, 1, ..., 2n-2}| = 2n-1, you see that there is one person for each possibility. If the person who shook 0 hands is not the partner of the person who shook 2n-2 hands, then this 0-person shook the hands of the 2n-2-person, since the 2n-2 person shook everyone's hands but his partner (which we assume is not the 0-person) and himself (which cannot be the 0-person because the 0-person is the 0-person, not the 2n-2 person). But this means the 0-person shook someone's hand, contradiction, thus the 0-person must be the 2n-2-person's partner. Remove this couple, and you will find that everyone's number of hand shakes must decrease by 1. Since there was someone with 1 handshake, he must become the 0-person. There was also a 2n-3-person who becomes the 2n-4 person. You're also now left with 2n-2 people, or 2n-3 people other than yourself. Since everyone's number of handshakes uniformly changed (decreased by 1) they're still all different, and noting that |{0, ..., 2n-4}| = 2n-3, you can use similar reasoning to see that the least and most are paired together. The people who now have 0 and 2n-4 handshakes originally really had 1 and 2n-3. Eliminating these people and following similar reasoning, you will see that the 2 and 2n-4 people are paired together, and in general, the m and 2n-2-m are paired together. This should give the desired result.

 

[RandallB]

What I'm still not sure of is exactly why all highest and lowest numbers of handshakes have to be coupled. I do see why this is the case for the extremes though. If we choose an arbitrary couple and assume that person "A" shakes hands with everyone except himself and his partner, only his partner has shaken hands with 0 people now. If we move to a second arbitrary couple and say that person "A" in that couple shakes hands with everyone except the 0-shake person from the previous couple and his partner, we are left with a couple with n-1 and 0+1 shakes where n is the maximum possible number of shakes. I suppose through induction it is apparent that this will continue until we reach a median, which must be paired. Now that I think about it, this may actually be a sufficient proof.

Yes that seems a a sufficient proof. . Ref: the old thread
https://www.physicsforums.com/showthread.php?t=64067
Also, to test it consider exchanging the pairings of two of the low shakers partners, say the two shake and three shakers to trade parners. Note that they have shaken with each other. While the lower count (in this case 2) has not shaken with etheir of their partners so trading is not a problem. BUT the higher count (3 here) has shaken with the others partner inorder to get the count up to three, therefore the trade cannot be allowed as it would require shaking hands with the new partner which is not allowed - and can only be fixed by shaking hands with the former partner instead.

 

[Greg825]

Thanks for the responces. It's such a fun problem.