HMMT 十一月 2020 · 团队赛 · 第 2 题

HMMT November 2020 — Team Round — Problem 2

[25] How many ways are there to arrange the numbers { 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.

解析

[25] How many ways are there to arrange the numbers { 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. Proposed by: Daniel Zhu Answer: 36 ( ) 3 Solution: Note that 6 can only be adjacent to 1, 5, and 7, so there are = 3 ways to pick its 2 neighbors. Since each of 1, 5, and 7 is relatively prime to every number in { 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 } so that no two of 2, 4, and 8 are adjacent. There are 3! · 2! = 12 ways of doing so, so the final answer is 3 · 12 = 36.