5
$\begingroup$

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?

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

0

You must log in to answer this question.

Browse other questions tagged .