0
$\begingroup$

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.

Thanks in advance!

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

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fleablood Jul 8 at 5:37
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Rotations are the same, so I think this overcounts by a factor of 3 $\endgroup$ – boink Jul 8 at 5:18
  • $\begingroup$ 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. $\endgroup$ – Arthur Jul 8 at 5:19
  • $\begingroup$ @fleablood I just meant that the problem statement says they're the same $\endgroup$ – boink Jul 8 at 5:22
  • $\begingroup$ "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$. $\endgroup$ – fleablood Jul 8 at 5:22
  • $\begingroup$ "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. $\endgroup$ – fleablood Jul 8 at 5:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.