# How many ways to of place $1, 2, 3, \dots, 9$ in a circle so the sum of any three consecutive numbers is divisible by $3.$

Determine the number of ways of placing the numbers $$1, 2, 3, \dots, 9$$ in a circle, so that the sum of any three numbers in consecutive positions is divisible by $$3.$$ (Two arrangements are considered the same if one arrangement can be rotated to obtain the other.)

I've experimented with possible combinations and found that it works when we put a multiple of 3 next to a number one more than a multiple of three beside a number that is two more than a multiple of 3. If we continue with this pattern around the circle, it works.

However, I'm curious in finding a more systematic approach than listing out all different combinations.

• Well consider the numbers in position $k$ and $k+3$ will have to be congruent $\mod 3$.. – fleablood Jul 8 at 5:08

In general, suppose we have the numbers $$1,2,\dots,3n$$, and we would like to place them in a circle so that the sum of any three consecutive terms is divisible by $$3$$.

Observe that the numbers at positions $$k$$ and $$k+3$$ must always be congruent modulo $$3$$. Thus we can partition the points along the circle into three sets which stand for the residues modulo $$3$$ of the positions. If we fix the number $$1$$ at, say, position $$1$$, then this tells us that every point at position $$3k+1$$ has residue $$1$$ modulo $$3$$.

Now we have a choice: either the numbers at positions $$3k+2$$ have residue $$0$$, or they have residue $$2$$. Either way, note that each of the three "partition classes" can be arranged in $$n!$$ different ways, giving us $$2(n!)^3$$ possibilities.

In this particular case, $$n=3$$, and the answer is $$432$$ (if rotations are counted as the same).

• If rotations are the same we can assume position $1$ has $3$. Then positions $4$ and $9$ have $6$ and $9$. there are $2$ ways to do that. position $2$ is either $\pm 1\pmod 3$. There are $2$ choices. position $2\equiv position 5\equiv position 8$ so there are $3!$ ways to do that. And $position 3\equiv position 6\equiv \position 9$ so there are $3!$ ways to do that. So there are $2*2*6*6=144$ ways if rotations are counted the same. If reflections are counted the same there are $2*6*6=72$ ways. – fleablood Jul 8 at 5:37

Brain storming. If we label the number positions as $$a_1,.....,a_9$$ then $$a_k+a_{k+1} + a_{k+2} \equiv 0 \equiv a_{k+1} + a_{k+2} + a_{k+3}\pmod 3$$ so $$a_k\equiv a_{k+3}\pmod 3$$.

The there are only three equivalence classes each with $$3$$ elements and so $$a_3, a_6, a_9$$ must all contain elements from one equivalence class. There are $$3$$ choices of which class and $$3!$$ ways to place the elements. $$a_1, a_4, a_7$$ must also contain elements from one equivalence class and there are $$2$$ choices of classes and $$3!$$ ways to arrange them. and for $$a_2, a_5, a_8$$ there is one choice of classe and $$3!$$ ways to arrange them.

So there $$3*3!*2*3!*1*3! = 6^4$$ ways to do this.

As rotations are considered the same (but not mirror symmetries???) divide by $$9$$.

So the answer is $$\frac {6^4}9$$.

• Rotations are the same, so I think this overcounts by a factor of 3 – boink Jul 8 at 5:18
• Since we're placing them in a circle, it's possible we ought to divide by 9 or maybe 18 to get rid of the symmetric options (equivalently, require $a_1=1$, and possibly divide by 2). It's hard to tell, though. – Arthur Jul 8 at 5:19
• @fleablood I just meant that the problem statement says they're the same – boink Jul 8 at 5:22
• "Since we're placing them in a circle" Placing the them in a circle means that $a_1$ is congruent to $a_8$. It DOESN"T mean that rotations are considered to be the same any more than Mr. Left in a word problem means you need to subtract. But if rotations are the same then divide by $9$. If symmetry is considered the same divide by $18$. – fleablood Jul 8 at 5:22
• "I just meant that the problem statement says they're the same" Oh, I didn't see that part. That's one of my pet peeve. If Mr. Left works $8$ hours a day, $5$ days a week how many hours a week does he work. Answer: Well, since the problem contains the word "left" that means we subtract so the answer is $8-5=3$. And question. How many ways are there to place people are a table. Answer: As the problem contains the word "table" and tables are circles rotations are the same.... No, they aren't unless the question says they are. – fleablood Jul 8 at 5:28