Mock AIME I 2012 Problems/Problem 2
Problem
A permutation of the numbers , , , , 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 is the first number of the permutation, then the second number cannot be or This gives ways to order the odd numbers and 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 is the last number. Thus there are golden numbers in which is the first or last number.
If is not the first or last number, then the numbers on either side of it must be and leaving and to occupy the other spots. There are ways to order the odd numbers and ways to order the other even numbers in this case. As the itself can occupy any of places that are not the first or last in the permutation, the number of such golden permutations is
Hence there are 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 and ) 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 is not the first number of the permutation, then it must be adjacent to the consecutive odd pair. There are such golden permutations here.
If 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 such golden permutations. If not, there are such golden permutations.
Hence there are golden permutations in Case 2.
We get golden permutations altogether.
Solution by Sylvia104