For which values of positive integer k is it possible to divide the first 3k positive integers into three groups with the same sum?

Question

I'm on a GCSE-a level syllabus currently, and I can't seem to think of any algebraic equation that I could comprise to solve this (with the GCSE/early a level syllabus). The question in full is

For which values of positive integer k is it possible to divide the first 3k positive integers into three groups with the same sum? (e.g. if k = 3, then the first 3k integers are 1,2,3,4,5,6,7,8,9. You can split these into 3 groups of 15, for example {{1,2,3,4,5},{7,8},{6,9}}. so it is possible for k=3)

Any help would be appreciated. Thanks

Answer 1

When I were a lad... we did lots of combinatorics at A-level. Shame it's gone, it's good grounding for a lot of university maths.

This is a nice example of applying algebra to combinatorics. Thank you for the question!

As a starter, consider the case where $k$ is even. In this case you can pair off numbers so they sum to $k+1$ (and recall the story of Gauss being asked to sum the numbers 1 to 100). The number of pairs is still a multiple of 3 so group them any way you like!

Next consider the case $k=3$. You have a solution to that in your question, but there are lots of other solutions. Ever seen the magic square?

$$\begin{array}{ccc} 6 & 1 & 8 \\ 7 & 5 & 3 \\ 2 & 9 & 4 \end{array} $$ There are 2 solutions here, grouping by row or column. Each row has exactly one number from each of $\{1,2,3\}$, $\{4,5,6\}$ and $\{7,8,9\}$. Also, it has exactly one number of each remainder modulo 3. Same goes for the columns. This guarantees that the sums are the same.

So you can see there are various approaches to this sort of problem. It's good practice to explore!

Ok, for the general case where $k$ is odd. Let's do an example, with $k = 7$ to illustrate.

Write all your numbers in 3 rows. $$\begin{array}{ccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ 15 & 16 & 17 & 18 & 19 & 20 & 21 \end{array} $$ The middle row is fine. The top row is too small and the bottom row is too large. Specifically, we need to add $49 = 7^2 = k^2$ to the top row, and subtract the same from the bottom. The natural approach is swap elements.

If we swap elements in the same column, e.g. 3 and 17, we improve our position by $14 = 2k$. We can do this at most $3 = (k-1)/2$ times and have $7 = k$ left over. Oh dear! That doesn't quite work, as we can't do a difference of 7. The smallest replacement is (7,15) which gives us 8.

So let's compensate. We perform 2 swaps with difference 14, one with 13 and one with 8. The difference 8 has to use (7,15) and we have 5 columns remaining to find the other differences. So (6,20), (5,19) and (4,17) will work.

For general $k$ we do $(k-3)/2$ swaps with difference $2k$, one swap with difference $2k-1$ and the minimal swap having difference $k+1$.

Just to make sure we never run out of space, The small swap uses up the outer 2 columns. The difference-$2k$ swaps use a further $(k-3)/2$ columns. We need 2 more columns for the difference $2k-1$.

So we require $$ (k-3)/2 + 4 \le k $$ and this is valid for $k \ge 5$.

So, not only can this be solved as stated for any $k \ge 2$, but we have an added extra in that we can guarantee that all the groups are the same size.

Answer 2

Assume $k\ge 2$ (For $k=1$ there is no solution)

The required sum is $$\frac{3k^2+k}{2}$$

The sum of the numbers $\ k+1,\cdots,2k\ $ is $$k^2+\frac{k(k+1)}{2}=\frac{3k^2+k}{2}$$

In the case of $k$ even, the numbers $\ 1,\cdots ,\frac{k}{2}\ $ and the numbers $\ 2k+\frac{k}{2}+1,\cdots ,3k\ $ together have the required sum, so we have found possible partitions.

In the case of $k$ odd, the sum of the numbers $\ 1,\cdots,\frac{k+1}{2}\ $ and the numbers $\ 2k+\frac{k+3}{2},\cdots ,3k$ and the number $k$ is the required sum, so we have found possible partitions again.

The key to calculate the sums is the formula $$\sum_{j=1}^k j =\frac{k(k+1)}{2}$$ and counting the number of "$2k's$" (Try it)

Answer 3

The sum of the first $3k$ numbers is $\frac 12(3k)(3k+1)$, so we want three groups that sum to $\frac 12k(3k+1)$. Clearly $k=1$ doesn't work because the desired sum is $2$ and we have a $3$ which is too big. $k=2$ does work as we have $7=1+6=2+5=3+4$. Intuitively, as we have more numbers we have more freedom, so expect it to work. You have shown a solution for $k=3$. Now note any number greater than $1$ can be expressed as a sum of $2$s and $3$s, so we can separate $3k$ into a sum of runs of $6$ and $9$. Our examples have the feature that each group is the same size, so we can add a constant to each entry and get a division of the numbers from $m$ to $m+5$ or $m+8$ into three groups. Each run can be treated as one of our examples, so the problem can be solved for all $k \gt 1$