Online Course Discussion Forum
2012 AIME II #14
I was doing some past AIME's when I came across #14 on the AIME II. The problem reads as follows:
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$.
I couldn't understand the solution and how it was able to choose who shook hands with who.
Think of it as a graph theory problem. Each person is a vertex, and if they shake hands, connect them with an edge. Because every vertex has exactly two edges, the $9$ vertices are all in cycles of lengths at least $3$. This fact is very easy to prove.
There are $4$ cases. (1) $3$ cycles of length $3$. (2) $2$ cycles of lengths $4$ and $5$. (3) $2$ cycles of lengths $3$ and $6$. (4) All $9$ vertices are in one big cycle.
In each case you have to choose the vertices in each cycle and count the circular permutations, remembering that reversing order does not count as a new arrangement. Also, in case (1), the order of the $3$ cycles does not matter.
Social networks