2019 Mock AMC 10B Problems/Problem 20

Revision as of 11:59, 4 November 2019 by Baker77 (talk | contribs)

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 exist next to each other, 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. The $1$ and $5$ are relatively prime to all numbers in this set, so there is no direct restriction on them. The number of cases is $12( 3 \cdot 2 \cdot 1 - 2) = 48$.

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. The $1$ and $5$ are relatively prime to all numbers in this set, so there is no direct restriction on them. The number of cases us $12(3 \cdot 2 \cdot 1 - 4) = 24$.

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