How many ways are there to arrange the numbers in a circle so that every two adjacent elements are relatively prime? Consider rotations and reflections of the same arrangement to be indistinguishable.
Solution
Note that 6 can only be adjacent to 1, 5, and 7, so there are ways to pick its neighbors. Since each of 1, 5, and 7 is relatively prime to every number in but itself (and hence can have arbitrary neighbors), without loss of generality suppose we have picked 1 and 5 as neighbors of 6. Observe that fixing the positions of 1, 5, and 6 eliminates the indistinguishability of rotations and reflections. Now, we have to consecutively arrange so that no two of 2, 4, and 8 are adjacent. There are ways of doing so, so the final answer is
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.