0
$\begingroup$

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!

$\endgroup$
1
1
$\begingroup$

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$)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.