Okay, perhaps this is a really stupid question but it has been puzzling me for a long time. I am preparing GRE general test, and in every test preparing book, there is also a counting question of shaking hands.
I have encountered the following two questions:
In a room of 10 people, each people need to shake hands with exactly 3 people, what is the total number of handshakes? (Shaking hand with oneself does not count.)
For this question, the solution is just $\frac{3\times 10}{2}=15$. Basically it lets each one to shake hands with three people, and then it double counts since A shaking hands with B means B shaking hands with A as well.
Another version of question is that:
In a room of 10 people, if each person shakes exactly once with others, what is the total number of handshakes? (Again shaking hand with oneself does not count.)
This has a general formula: if the room is of $n$ people, then the total number of hand shakes is $n(n-1)/2$.
These kind of questions really puzzle me, since it seems no general solution for them. For example, what if in a room $10$ people, I want each people to shake hands with exactly $2$ people? what if $5$ people? what if the room is of $n$ people?
There have been some posts in the stack exchange, but what I have seen are individual cases. Is it possible for a general formula? For example, in a room of $n$ people, shaking hands exactly with $k$ people?
Thank you!
Best Answer
This can be generalized even more. If you have $n$ people, $p_1, p_2,..., p_n$ and you want $p_i$ to shake hands with $a_i$ people, then do the follwoing:
Make a graph in which every vertex is a person and draw an adge between any 2 people that shake hands. Observer that $deg(p_i)=a_i$, $\forall i$, so the number of handshakes, i.e. the number of edges is $$\frac{\sum_{i=1}^{n}deg(p_i)}{2}=\frac{\sum_{i=1}^{n}a_i}{2}$$
Important: for the handskaes to be possible, $\sum_{i=1}^{n}a_i$ must be even.
So to answer your question, if we have $n$ people and each should shake hands with $m$ people, for this to be possible $mn$ must be even and we have $$\frac{\sum_{i=1}^{n}a_i}{2}=\frac{mn}{2}$$
(because $a_1=a_2=...=a_n=m$)