Online Course Discussion Forum

2012 AIME II #14

 
 
Picture of Dr. Kevin Wang
Re: 2012 AIME II #14
by Dr. Kevin Wang - Monday, 10 August 2020, 12:01 AM
 

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.