2019 Mock AMC 10B Problems/Problem 20

Problem

Define a permutation $a_1a_2a_3a_4a_5a_6$ of the set $1, 2, 3, 4, 5, 6$ to be $\text{ factor-hating }$ if $\text{ gcd }(a_k, a_{k+1}) = 1$ for all $1 \leq k \leq 5$ . Find the number of $\text{ factor-hating }$ permutations.

$\textbf{(A) }36 \qquad \textbf{(B) }48 \qquad \textbf{(C) }56 \qquad \textbf{(D) }64 \qquad \textbf{(E) }72 \qquad$

Solution

No even numbers can be neighbors, since they are divisible by $2$ . This leaves $4$ possible sequences for the even numbers to occupy: $(a_1, a_3, a_5)$ , $(a_2, a_4, a_6)$ , $(a_1, a_3, a_6)$ , and $(a_1, a_4, a_6)$ .

Case #1: There are $2 + 2 + 4 + 4 = 12$ cases where the $6$ is on the end of a sequence. If so, there is $1$ place where the $3$ cannot go. Since $1$ and $5$ are relatively prime to all numbers in this set, there is no direct restriction on them. The number of cases $= 12( 3 \cdot 2 \cdot 1 - 2) = 48$ . ( $-2$ represents the number of cases with a $3$ next to a $6$ .)

Case #2: There are $2 + 2 + 4 + 4 = 16$ cases where the $6$ is in the middle of a sequence. If so, there are $2$ places where the $3$ can go. Since $1$ and $5$ are relatively prime to all numbers in this set, there is no direct restriction on them. The number of cases $= 12(3 \cdot 2 \cdot 1 - 4) = 24$ . ( $-4$ represents the number of cases with a $3$ next to a $6$ .)

Therefore, the number of factor-hating permutations $= 24 + 48 = \boxed{\text{(E)}72}$ .

Page

Toolbox

Search

2019 Mock AMC 10B Problems/Problem 20

Problem

Solution