Find all permutations of the numbers 1,2,…,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 and 5)+C(6 and 4)+C(4 and 5))+C(6 and 5 and 4)
Where C(condition) means the number of ways for that condition to be satisfied.
Now we have:
9!−(8!⋅2!⋅2!⋅3 - (7!⋅2!2⋅2!2⋅3)+(6!⋅2!3⋅2!3))
Finally, this evaluates to be 104⋅6! or 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!⋅2!. A similar method is used for the other ones. The ⋅3 is because the cases are symmetric.