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?