Ordered Arrangements: number of ways of arranging $1-9$ in a circle so that sum of 3 adjacent is divisible by 3

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.)

I worked out that if I have the numbers in ascending/descending order, it will be divisible by $3$ (because $x-1 + x + x+1$ would be equal to $3x$). I'm not sure how to use that information to work out the total number though (or if there are other ways to place them).

Please provide an answer to my question and help me with how to proceed with my approach.

Answer 1

Hint: $a_1 \equiv a_4 \equiv a_7 \pmod 3$.

Likewise for the other indices.

This gives us a constraint, dividing up into 3 sets of 3. Under this constraint, all permutations work.

Hence $ \dfrac{3!\times (3!)^3}{9} = 144$ ways.

Answer 2

Hint: You have $3$ numbers of the form $3k$, $3$ of the form $3k+1$ and $3$ of the form $3k−1$.

Start with fixing a $3k$ at the start.

If you put another $3k$ after it, will the resulting combination $3k,3k,...$ be possible?

No, because that would demand another $3k$ after it ($\because$ sum of $3$ consecutive numbers must be divisible by $3$)
and so on, and the whole arrangement would need to be of the form $3k,3k,3k,3k,3k,...$ which is impossible.

Conclude you only have $2$ possibilities of arrangement

1. $3k,3k+1,3k−1,3k,3k+1,...$
   
2. $3k,3k−1,3k+1,..$
   

(the second is the mirror of the other).

Suppose we start with $3k,3k+1$.
Then, we would need a number of the form $3k-1$ after that for the sum $(3k)+(3k+1)+?$ to be divisible by $3$.
Now, we have $3k,3k+1,3k-1,..$.
For the sum $(3k+1)+(3k-1)+?$ to be divisible by $3$ we need to have a $3k$ after $3k-1$ giving us $3k,3k+1,3k-1,3k,..$.

Calculate the number of possibilities in any one. Double that is the answer.

Answer 3

First, when we look at this problem we must think what does every set of 3 numbers contain. Since, $1 + 2 + 3 \equiv 0 \mod 3$ and $2 + 3 + 4 ≡ 0 \mod 3$ then $1 + 2 + 3 \equiv 2 + 3 + 4 \mod 3$. So $1 ≡ 4 \mod 3$.

Then we use the same tactic to find that $4 ≡ 7 \mod 3$. So $1 ≡ 4 ≡ 7 \mod 3$. Then we also find that $2 ≡ 5 ≡ 8 \mod 3$ and $3 ≡ 6 ≡ 9 \mod 3$. And since $1 + 2 +3 ≡ 0 \mod 3$, we realize that a set of 3 must have one number from each set.

We should start by putting $1$ on top to account for rotational symmetry. Then we have $2$ choices for which set to be to the right of the one. Then we have $3$ choices for which number from the set shall go there. Then there are $3$ choices for the number to the right of that one because there are $3$ numbers from the set that we did not use so far. Then there are $2$ choices for the number that goes to the right of that because we already used $1$ from that set. Then another $2$ for the next. and $2$ for the next. then there is only one option for how to arrange the rest of the numbers because there is only one number left from each set.

So there are $2 * 3 * 3 * 2 * 2 * 2 * 1 = 144$ total ways to arrange the numbers $1-9$ in a circle if the sum of every $3$ adjacent numbers must be divisible by $3$.