Question

In a group of nine people each person shakes hands with exactly two of the other people from the group. Let N be the number of ways this handshaking can occur. Consider two handshaking arrangements different if and only if at least two people who shake hands under one arrangement do not shake hands under the other arrangement. Find the remainder when N is divided by 1000

Answer 1

We can solve this problem using the principle of counting, specifically the handshaking lemma.

The handshaking lemma states that in a group of 2n people, where each person shakes hands with exactly one other person, the number of handshaking arrangements is equal to n!.

In this case, we have 9 people, so n = 4.5. Each person shakes hands with exactly two other people, so the number of handshaking arrangements is (4.5!) / (2!)^4 = 945.

Finally, the remainder when N is divided by 1000 is 945 % 1000 = 945.

Explanation: