Question

Find the number of ways of arranging the numbers

1,2,3,...9 in a circle, so that the sum of any three adjacent numbers is divisible by 3. (Two arrangements are considered the same if one arrangement can be rotated to obtain the other.)

Answer 1

First of all, note that all integers are either 0,1, or 2 modulo 3 (if you're not familiar with this terminology, it means that every integer is either a multiple of 3, or it is 1 or 2 away from a multiple of 3).

So, we can think of our numbers as

`\begin{array}cx&x\mod 3\\0&0\\1&1\\2&2\\3&0\\4&1\\5&2\\6&0\\7&1\\8&2\\9&0\end{array}`

In order to make sure that the sum of any three adjacent numbers is divisible by 3, we have to make sure that any group of 3 three adjacent numbers contains a 0, a 1 and a 2. This is possible only if we arrange our 9 numbers in 3 groups of 3 numbers containing 0,1 and 2 exactly once, repeating always the same pattern.

For example, we could arrange our numbers following the pattern

`0,1,2,0,1,2,0,1,2`

or

`2,0,1,2,0,1,2,0,1`

We have
`3!=6` possible patterns. Suppose for example that we choose the pattern

`0,1,2,0,1,2,0,1,2`

One possible way of following this pattern would be the arrangement

`3,1,2,6,4,5,9,7,8`

In fact, we substituted every '0' with a multiple of 3 (3, 6 or 9), every '1' with a number 1 away from a multiple of 3 (1, 4 or 7) and every '2' with a number 2 away from a multiple of 3 (2, 5 or 8).

This means that, once we fix a patter, we have 3 choices for the first 3 slots, 2 choices for the next 3 slots, and the final slot will be fixed. So, we have

`3\cdot 3\cdot 3\cdot 2 \cdot 2 \cdot 2 = 216`

possible ways of following a fixed pattern. Since the number of patterns was 6, we have

`216\cdot 6 = 1296`

possible arrangements.