# Grouping natural numbers into arithmetic progression

I need to find the number of ways of dividing the first 12 natural numbers into 3 equal groups (4 numbers each), so that the numbers in any particular group can be arranged in AP (Arithmetic progression).

This is what I did:

Consider the group which contains the number $1$

For this group the possibilities are:

$1- 2 -3- 4$ or, $1- 3 -5- 7$ or, $1- 4 -7- 10$

Clearly 12 is not included in any one of these groups, so $12$ must be part of another group. For this group too we get three possibilities (counting backwards from $12$). After that, I just checked every possible combination of the two groups to see if the third was in AP. (it was kind of easy, just 9 cases)

I got my final answer as 4. I'd like to know if there is more simple and elegant method to solving this, and if possible generalizing for the first n natural numbers.

• +1-a great approach. Find the easy constraints (which takes some thought), then realize you are down to few enough possibilities to check with the tools at hand. Commented May 18, 2013 at 4:23

This is an interesting question. I don't have a real answer but I wrote a program to calculate values for different $n$ and $m$, counting the number of ways to split the first $n$ numbers into groups of arithmetic sequences of size $m$ . Here are some results with the pairs are written as $(n,m)$:

$(9,3)=5$,

$(12,3)=15$, $(12,4)=4$,

$(15,3)=55$, $(15,5)=4$,

$(16,4)=11$,

$(18,3)=232$, $(18,6)=4$, $(18,6)=4$,

$(20,4)=23$, $(20,5)=10$,

$(24,3)=6643$, $(24,4)=68$, $(24,6)=10$, $(24,8)=4$.

I skipped writing pairs that satisfy these equations:

If $m$ is not a divisor of $n$ then $(n,m)=0$. If $n$ is even then

$$(n,\frac{n}{2})=2,$$

$$(n,2)=\frac{n!}{2^{n/2}\frac{n}{2}!}.$$

EDIT

This wouldn't fit in a comment, but here are the ways of grouping (12,3):

$$\begin{array}{ccc} \left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{array}\right] & \left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 9 & 11 \\ 8 & 10 & 12 \end{array}\right] & \left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 6 & 8 \\ 5 & 7 & 9 \\ 10 & 11 & 12 \end{array}\right]\\ \left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 7 & 10 \\ 5 & 8 & 11 \\ 6 & 9 & 12 \end{array}\right] & \left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 8 & 12 \\ 5 & 6 & 7 \\ 9 & 10 & 11 \end{array}\right] & \left[\begin{array}{ccc} 1 & 3 & 5 \\ 2 & 4 & 6 \\ 7 & 8 & 9 \\ 10 & 11 & 12 \end{array}\right]\\ \left[\begin{array}{ccc} 1 & 3 & 5 \\ 2 & 4 & 6 \\ 7 & 9 & 11 \\ 8 & 10 & 12 \end{array}\right] & \left[\begin{array}{ccc} 1 & 3 & 5 \\ 2 & 6 & 10 \\ 4 & 8 & 12 \\ 7 & 9 & 11 \end{array}\right] & \left[\begin{array}{ccc} 1 & 3 & 5 \\ 2 & 7 & 12 \\ 4 & 6 & 8 \\ 9 & 10 & 11 \end{array}\right]\\ \left[\begin{array}{ccc} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \\ 10 & 11 & 12 \end{array}\right] & \left[\begin{array}{ccc} 1 & 5 & 9 \\ 2 & 3 & 4 \\ 6 & 7 & 8 \\ 10 & 11 & 12 \end{array}\right] & \left[\begin{array}{ccc} 1 & 5 & 9 \\ 2 & 4 & 6 \\ 3 & 7 & 11 \\ 8 & 10 & 12 \end{array}\right]\\ \left[\begin{array}{ccc} 1 & 5 & 9 \\ 2 & 6 & 10 \\ 3 & 7 & 11 \\ 4 & 8 & 12 \end{array}\right] & \left[\begin{array}{ccc} 1 & 6 & 11 \\ 2 & 3 & 4 \\ 5 & 7 & 9 \\ 8 & 10 & 12 \end{array}\right] & \left[\begin{array}{ccc} 1 & 6 & 11 \\ 2 & 7 & 12 \\ 3 & 4 & 5 \\ 8 & 9 & 10 \end{array}\right] \end{array}$$

• How is (12,3) = 15 can you print the possibilities? Commented May 18, 2013 at 9:03
• @Quark I edited the possibilities for (12,3) into my answer. Commented May 18, 2013 at 13:04