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 "2019 Mock AMC 10B Problems/Problem 20"
Line 7: Line 7:
 
==Solution==  
 
==Solution==  
  
−
No even numbers can exist next to each other, since they are divisible by <math>2</math>. This leaves <math>4</math> possible sequences for the even numbers to occupy: <math>(a_1, a_3, a_5)</math>, <math>(a_2, a_4, a_6)</math>, <math>(a_1, a_3, a_6)</math>, and <math>(a_1, a_4, a_6)</math>.  
+
No even numbers can be neighbors, since they are divisible by <math>2</math>. This leaves <math>4</math> possible sequences for the even numbers to occupy: <math>(a_1, a_3, a_5)</math>, <math>(a_2, a_4, a_6)</math>, <math>(a_1, a_3, a_6)</math>, and <math>(a_1, a_4, a_6)</math>.  
  
 
Case #1: There are <math>2 + 2 + 4 + 4 = 12</math> cases where the <math>6</math> is on the end of a sequence. If so, there is <math>1</math> place where the <math>3</math> cannot go. The <math>1</math> and <math>5</math> are relatively prime to all numbers in this set, so there is no direct restriction on them. The number of cases is <math>12( 3 \cdot 2 \cdot 1 - 2) = 48</math>. (<math>-2</math> represents the number of cases with a <math>3</math> next to a <math>6</math>.)
 
Case #1: There are <math>2 + 2 + 4 + 4 = 12</math> cases where the <math>6</math> is on the end of a sequence. If so, there is <math>1</math> place where the <math>3</math> cannot go. The <math>1</math> and <math>5</math> are relatively prime to all numbers in this set, so there is no direct restriction on them. The number of cases is <math>12( 3 \cdot 2 \cdot 1 - 2) = 48</math>. (<math>-2</math> represents the number of cases with a <math>3</math> next to a <math>6</math>.)

Revision as of 11:01, 4 November 2019

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 be neighbors, 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$. ($-2$ represents the number of cases with a $3$ next to a $6$.)

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$. ($-4$ represents the number of cases with a $3$ next to a $6$.)

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2019_Mock_AMC_10B_Problems/Problem_20&oldid=110882"