Maths Olympiad Prep

Library / /287 of 348

Combinatorics Difficulty 5.1 AIME, harder Find the answer

How many ways are there to arrange the numbers {1,2,3,4,5,6,7,8}\{1,2,3,4,5,6,7,8\} in a circle so that every two adjacent elements are relatively prime? Consider rotations and reflections of the same arrangement to be indistinguishable.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Note that 6 can only be adjacent to 1, 5, and 7, so there are (32)=3\binom{3}{2}=3 ways to pick its neighbors. Since each of 1, 5, and 7 is relatively prime to every number in {1,2,3,4,5,6,7,8}\{1,2,3,4,5,6,7,8\} 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 {2,3,4,7,8}\{2,3,4,7,8\} so that no two of 2, 4, and 8 are adjacent. There are 3!2!=123!\cdot 2! = 12 ways of doing so, so the final answer is 312=363 \cdot 12=36

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.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.