Relatively Prime Consecutive Digits
Six-digit integers will be written using each of the digits $ 1 $ through $ 6 $ exactly once per six-digit integer. How many different positive integers can be written such that all pairs of consecutive digits of each integer are relatively prime? (Note: $ 1 $ is relatively prime to all integers.)
- 1
- 2
- 3
- +
- 4
- 5
- 6
- -
- 7
- 8
- 9
- $\frac{a}{b}$
- .
- 0
- =
- %
- $a^n$
- $a^{\circ}$
- $a_n$
- $\sqrt{}$
- $\sqrt[n]{}$
- $\pi$
- $\ln{}$
- $\log$
- $\theta$
- $\sin{}$
- $\cos{}$
- $\tan{}$
- $($
- $)$
- $[$
- $]$
- $\cap$
- $\cup$
- $,$
- $\infty$
Solution
First, we observe that the only pairs of integers from 1 to 6 that fail to be relatively prime are any pair of even integers as well as the pair (3, 6). If we temporarily ignore the pair (3, 6), we can focus only on parity. We must arrange the six digits in such a way that no two even digits are consecutive. Using $ \color{blue}e $ to denote even and $ o $ to denote odd, this gives us four different possible arrangements:
\begin{align}
{\color{blue}e} o {\color{blue}e} o {\color{blue}e} o \\
o {\color{blue}e} o {\color{blue}e} o {\color{blue}e} \\
{\color{blue}e} o {\color{blue}e} o o {\color{blue}e} \\
{\color{blue}e} o o {\color{blue}e} o {\color{blue}e
}\end{align}
For any of these four arrangements, there are $3!$ ways to select the three even numbers and $3!$ ways to select the three odd numbers, for a total of $3!\cdot 3!= 36$ total arrangements. Hence, ignoring the issue of (3, 6) adjacencies, we have $ 36 \cdot 4 = 144 $ such numbers.
Now, we must count the number of the above arrangements that include any (3, 6) adjacencies and subtract them off. Let's consider the number of (3, 6) adjacencies in arrangement $ (1) $. Suppose that the first digit is 6. Then if the second digit is 3, there are $ 2!\cdot 2!= 4 $ arrangements of the remaining digits. So there are 4 arrangements that go 6 3 _ _ _ _. If instead the third digit is 6, then by similar reasoning, there are 4 arrangements that go _ 3 6 _ _ _, and 4 arrangements that go _ _ 6 3 _ _, for a total of 8 arrangements. By symmetry, there are also 8 arrangements that include a (3, 6) adjacency when the fifth digit is 6. So, there are a total of $ 4 + 8 + 8 = 20 $ arrangements of $ (1) $ that have 3 and 6 adjacent. By symmetry, there are also $ 20 $ arrangements of $ (2) $ that have 3 and 6 adjacent.
Finally, we must count the number of arrangements of $ (3) $ that have 3 and 6 adjacent. From previous reasoning, we see that if the 6 is on an endpoint, there are 4 arrangements with an adjacent 3, and if 6 is in the interior, there are 8 such arrangements. Hence, in this case, there are $ 4 + 8 + 4 = 16 $ arrangements that have 3 and 6 adjacent. Again, by symmetry, there are also $ 16 $ arrangements of $ (4) $ with 3 and 6 adjacent.
Overall, there are $ 20 + 20 + 16 + 16 = 72 $ arrangements that have 3 and 6 adjacent. So, our final answer is $ 144 - 72 = \boxed{72} $ numbers.
Freeflows