2019 Mock AMC 10B Problems/Problem 20
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
.
Case #1: 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
. (
represents the number of cases with a
next to a
.)
Case #2: 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
. (
represents the number of cases with a
next to a
.)
Therefore, the number of factor-hating permutations .