Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME I 2012 Problems/Problem 2"

(Created page with "==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 ...")
 
(→‎Solution)
 
Line 1: Line 1:
 +
==Problem==
 +
A permutation of the numbers <math>\{2</math>, <math>3</math>, <math>4</math>, <math>\cdots</math>, <math>9\}</math> is called ''golden'' if every two consecutive numbers in the permutation are relatively prime. How many ''golden'' permutations are there?
 +
 
==Solution==
 
==Solution==
 
'''Case 1: There are no consecutive odd numbers in the permutation'''
 
'''Case 1: There are no consecutive odd numbers in the permutation'''

Latest revision as of 10:13, 8 April 2012

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_I_2012_Problems/Problem_2&oldid=46202"