Mock AIME I 2012 Problems/Problem 2

Problem

A permutation of the numbers $\{2$, $3$, $4$, $\cdots$, $9\}$ is called golden if every two consecutive numbers in the permutation are relatively prime. How many golden permutations are there?

Solution

Case 1: There are no consecutive odd numbers in the permutation

Then either the even numbers occupy the even places and the odd numbers the odd places of the permutation, or else the even numbers are in the odd places and the odd numbers in the even places of the permutation.

If $6$ is the first number of the permutation, then the second number cannot be $3$ or $9.$ This gives $2\times3\times2\times1=12$ ways to order the odd numbers and $3!=6$ ways to order the other even numbers. Similarly there are 12 ways to order the odd numbers and 6 to order the other even numbers if $6$ is the last number. Thus there are $2\times12\times6=144$ golden numbers in which $6$ is the first or last number.

If $6$ is not the first or last number, then the numbers on either side of it must be $5$ and $7,$ leaving $3$ and $9$ to occupy the other spots. There are $2\times2=4$ ways to order the odd numbers and $3!=6$ ways to order the other even numbers in this case. As the $6$ itself can occupy any of $6$ places that are not the first or last in the permutation, the number of such golden permutations is $6\times4\times6=144.$

Hence there are $144+144=288$ golden permutations in Case 1.

Case 2: There is a consecutive pair of odd numbers in the permutation

There can be only one such consecutive pair (which obviously cannot consist of $3$ and $9$) and the first and last numbers of the permutation must both be even. Since the working is similar to Case 1, we omit the details.

If $6$ is not the first number of the permutation, then it must be adjacent to the consecutive odd pair. There are $96$ such golden permutations here.

If $6$ is the first or last number of the permutation, it can be adjacent to the consecutive odd pair, or not. If it is, there are $144$ such golden permutations. If not, there are $192$ such golden permutations.

Hence there are $96+144+192=432$ golden permutations in Case 2.

We get $288+432=\boxed{720}$ golden permutations altogether.

Solution by Sylvia104