Find all permutations of the numbers $1,2,\ldots,9$ in which no two adjacent numbers have a sum divisible by $7$ or $13$.
Problem
Source:
Tags: combinatorics
bigbrain123
13.04.2021 17:27
In search of a simpler complementary counting method, we list the number pairs that don't work for $7$ and $13$ respectively.
$7$ - ($1,6$) ($2,5$) ($3,4$)
$13$ - ($6,7$) ($8,5$) ($9,4$)
If we list the numbers in a row, with blanks to fill in for the potential numbers. $*$ will mean any left over number. $\_$ means the two possible numbers for the corresponding pair as listed above.
For example, here is one possible arrangement:
$\_ 6 \_ 5 \_ 4 \_ * *$
The reason why we choose $6$, $5$, $4$ is because they are the only numbers which are used in summing to make both $7$ and $13$. This makes the calculations much easier, as we can now bash it with PIE.
Therefore, we have: $9! - C(6) + C(5) + C(4) - (C(6 \text{ and } 5) + C(6 \text{ and } 4) + C(4 \text{ and } 5)) + C(6 \text{ and } 5 \text{ and } 4)$
Where $C( \text{condition})$ means the number of ways for that condition to be satisfied.
Now we have:
$9! - \big{(}8! \cdot 2! \cdot 2! \cdot 3$ - ($7! \cdot 2!^2 \cdot 2!^2 \cdot 3) + (6! \cdot 2!^3 \cdot 2!^3)\big{)}$
Finally, this evaluates to be $104 \cdot 6!$ or $\fbox{74,880}$
explanation for that countingWe treat a pair of numbers which sum up to $7$ or $13$ as a "package". For example, in the case of $C(6)$, we assume that $6$ and $1$ or $7$ as a package. This reduces it to be $8!$, since $6$ and $1$ is now a package. After that, we can choose either $1$ or $7$ and whether $6,7$ or $7,6$, which is why we have $2! \cdot 2!$. A similar method is used for the other ones. The $\cdot 3$ is because the cases are symmetric.