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 .