25. Vumos wants to write the integers 1 to 9 in the nine boxes shown so that the sum of the integers in any three adjacent boxes is a multiple of 3 . In how many ways can he do this?
A $6 \times 6 \times 6 \times 6$
B $6 \times 6 \times 6$
C $2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 2$
D $6 \times 5 \times 4 \times 3 \times 2 \times 1$
E $9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1$
SOLUTION
A

Let $a, b, c, d$ be the numbers in four adjacent boxes. Then both $a+b+c$ and $b+c+d$ must be multiples of 3 . Therefore $a-d$ is a multiple of 3. This applies to any entries three apart. So the numbers in the set $\{1,4,7\}$ must be listed three apart; and the same applies to $\{2,5,8\}$ and to $\{3,6,9\}$. This will automatically ensure that the sum of three adjacent numbers is a multiple of 3 .

There are 3 choices about which of these sets go in the first, fourth and seventh boxes, 2 choices for the next set and 1 for the third. Also there are $3 \times 2 \times 1=6$ choices for which order the numbers in each set are given. That gives the total number of choices as $6 \times 6 \times 6 \times 6$.