# In how many ways can numbers $\in \{1, 2, ..., 3n \}$ be arranged in such way that the sum of every $3$ consecutive numbers is divisible by $3$?

In how many ways can the numbers from the set $$\{1, 2, ..., 3n \}$$ be arranged in a sequence such that the sum of every three consecutive numbers is divisible by $$3$$?

Solution:

All the numbers from the set $$\{1, 2, ..., 3n \}$$ can be divided in 3 subsets:

1. numbers that are equal to $$0$$ mod $$3$$
2. numbers that are equal to $$1$$ mod $$3$$
3. numbers that are equal to $$2$$ mod $$3$$

The only possible groups of $$3$$ numbers with sums divisible by $$3$$ are therefore:

• element from group $$1$$ + element from group $$1$$ + element from group $$1$$
• element from group $$2$$ + element from group $$2$$ + element from group $$2$$
• element from group $$3$$ + element from group $$3$$ + element from group $$3$$
• element from group $$1$$ + element from group $$2$$ + element from group $$3$$

When I want to make sum of every three consecutive numbers be divisible by $$3$$, I can start with choosing the first $$3$$ numbers of sequence and then moving my 'window' containing 3 numbers by $$1$$ place to the right. That way, by moving my 'window' I will lose one number on the left and get one new on the right. After such move, for the numbers in the 'window' to maintain divisibility by $$3$$ I need to add a number that shares the same group with the number that I left outside of my window.

By extension, I can conclude that if I need a sequence such that the sum of every three consecutive numbers is divisible by $$3$$, I have to structure every another window of 3 numbers the same way as the first one. Therefore my sequences can look like that:

1. | $$g1$$ + $$g1$$ + $$g1$$ | $$g1$$ + $$g1$$ + $$g1$$ | $$g1$$ + $$g1$$ + $$g1$$ | ...
2. | $$g2$$ + $$g2$$ + $$g2$$ | $$g2$$ + $$g2$$ + $$g2$$ | $$g2$$ + $$g2$$ + $$g2$$ | ...
3. | $$g3$$ + $$g3$$ + $$g3$$ | $$g3$$ + $$g3$$ + $$g3$$ | $$g3$$ + $$g3$$ + $$g3$$ | ...
4. | $$g1$$ + $$g2$$ + $$g3$$ | $$g1$$ + $$g2$$ + $$g3$$ | $$g1$$ + $$g2$$ + $$g3$$ | ...

Now we can see that first $$3$$ sequences are impossible, because in my set of numbers I have $$n$$ elements from group $$1$$, $$n$$ elements from group $$2$$, $$n$$ elements from group $$3$$ and they all need to be placed in my sequence. Therefore the only scheme that I can use is the last one:

| $$g1$$ + $$g2$$ + $$g3$$ | $$g1$$ + $$g2$$ + $$g3$$ | $$g1$$ + $$g2$$ + $$g3$$ | ...

Now, I need to permute the places of groups in each window of $$3$$ numbers: that can be done in $$3! = 6$$ ways. Then I need to permute numbers in their groups. Therefore, ultimately, I can create $$6 \cdot n! \cdot n! \cdot n!$$ such sequences.

Is that correct?

• I would have thought your $6 \cdot n! \cdot n! \cdot n!$ is like to be correct. Commented Mar 10 at 22:45
• closely related
– lulu
Commented Mar 10 at 22:55
• looks correct to me Commented Mar 11 at 3:46