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,...") |
(→Solution) |
||
(8 intermediate revisions by the same user not shown) | |||
Line 7: | Line 7: | ||
==Solution== | ==Solution== | ||
− | No even numbers can | + | 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. | + | 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. Since <math>1</math> and <math>5</math> are relatively prime to all available numbers, there is no direct restriction on them. The number of cases <math>= 12( 3 \cdot 2 \cdot 1 - 2) = 48</math>. (<math>-2</math> represents the number of permutations containing <math>3</math> next to <math>6</math>.) |
− | Case #2: There are <math>2 + 2 + 4 + 4 = | + | Case #2: There are <math>2 + 2 + 4 + 4 = 12</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. Since <math>1</math> and <math>5</math> are relatively prime to all available numbers, there is no direct restriction on them. The number of cases <math>= 12(3 \cdot 2 \cdot 1 - 4) = 24</math>. (<math>-4</math> represents the number of permutations containing <math>3</math> next to <math>6</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{\text{(E)}72}</math>. |
Latest revision as of 16:21, 8 November 2019
Problem
Define a permutation of the set
to be
if
for all
. Find the number of
permutations.
Solution
No even numbers can be neighbors, since they are divisible by . This leaves
possible sequences for the even numbers to occupy:
,
,
, and
.
Case #1: There are cases where the
is on the end of a sequence. If so, there is
place where the
cannot go. Since
and
are relatively prime to all available numbers, there is no direct restriction on them. The number of cases
. (
represents the number of permutations containing
next to
.)
Case #2: There are cases where the
is in the middle of a sequence. If so, there are
places where the
can go. Since
and
are relatively prime to all available numbers, there is no direct restriction on them. The number of cases
. (
represents the number of permutations containing
next to
.)
Therefore, the number of factor-hating permutations .