Difference between revisions of "2019 Mock AMC 10B Problems/Problem 20"
(Created page with "==Problem== Define a permutation <math>a_1a_2a_3a_4a_5a_6</math> of the set <math>1, 2, 3, 4, 5, 6</math> to be <math>\text{ factor-hating }</math> if <math>\text{ gcd }(a_k,...") |
|||
| Line 9: | Line 9: | ||
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 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>. | ||
| − | 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>. | + | [b]Case #1:[/b] 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>. |
| − | Case #2: There are <math>2 + 2 + 4 + 4 = 16</math> cases where the <math>6</math> is in the middle of a sequence. If so, there are <math>2</math> places where the <math>3</math> can 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 us <math>12(3 \cdot 2 \cdot 1 - 4) = 24</math>. | + | [b]Case #2:[/b] There are <math>2 + 2 + 4 + 4 = 16</math> cases where the <math>6</math> is in the middle of a sequence. If so, there are <math>2</math> places where the <math>3</math> can 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 us <math>12(3 \cdot 2 \cdot 1 - 4) = 24</math>. |
Therefore, the number of factor-hating permutations <math>= 24 + 48 = \boxed{72}</math>. | Therefore, the number of factor-hating permutations <math>= 24 + 48 = \boxed{72}</math>. | ||
Revision as of 10:59, 4 November 2019
Problem
Define a permutation 
of the set 
to be 
if 
for all 
. Find the number of permutations.
Solution
No even numbers can exist next to each other, since they are divisible by 
. This leaves 
possible sequences for the even numbers to occupy: 
, 
, 
, and 
.
[b]Case #1:[/b] There are 
cases where the 
is on the end of a sequence. If so, there is 
place where the 
cannot go. The and 
are relatively prime to all numbers in this set, so there is no direct restriction on them. The number of cases is 
.
[b]Case #2:[/b] There are 
cases where the is in the middle of a sequence. If so, there are places where the can go. The and are relatively prime to all numbers in this set, so there is no direct restriction on them. The number of cases us 
.
Therefore, the number of factor-hating permutations 
.
