Partition of $\{1,2,3,\cdots,3n\}$ into $n$ subsets, each with $3$ numbers, which have equal sum

I want to show, that for every odd $n$ $(n\ge3)$, there exists a partition of $\{1,2,3,\cdots,3n\}$ into $n$ disjoint subsets, where each one has $3$ elements and equal sum. The first such number is $3$. For $3$ it is obvious. $\{1,6,8\}, \{2,4,9\}, \{3,5,7\}$. I tried to show this using induction, but it seems I have some trouble with it. Please help me, if you can.

• Your example for $n=3$ doesn't work. The sums of the three subsets are $14,15$ and $16$. It should be $\{3,5,7\}, \{2,4,9\}$ and $\{1,6,8\}$. – Anurag A Feb 28 '16 at 8:42
• For $n=3$, either rows or columns of $3\times 3$ magic square will do. – Ng Chung Tak Feb 28 '16 at 9:58

We let $k$ range from $1$ to $n$. Our sets are $$\begin {cases} \{k, \frac{3n-1}2+k,3n+2-2k\} &1\le k \le \frac {n+1}2\\ \{k,n+k-\frac{n+1}2,4n-2k+2\}&\frac{n+1}2 \lt k \le n \end {cases}$$ These can be seen to add to $\frac {9n+3}2$ and to use the numbers $1$ to $n$ in the first entry, $n+1$ to $2n$ in the second and $2n+1$ to $3n$ in the third. They follow the pattern in Ng Chung Tak's answer for $n=5$

• slick !!!!!!!!! – Abr001am Feb 28 '16 at 16:30
• Still not right -- the sum in the second row is wrong. – TonyK Feb 28 '16 at 18:09
• @TonyK: got it this time. I had dropped a + the first time and didn't fix it right. Thanks – Ross Millikan Feb 28 '16 at 18:25

Let $S$ be the equal sum of each partition, then $nS=1+\ldots+3n$.

i.e. $\: nS=\frac{3n(3n+1)}{2} \implies S=\frac{3(3n+1)}{2}$

Now, $n=1$ is trivial and $n$ should be odd since the sum is an integer.

Note that the median of the sequence is $\frac{3n+1}{2}$.

Observing $1+\frac{3n+1}{2}+3n=S$

Take $a+b+c=0$:

$(1+a)+(\frac{3n+1}{2}+b)+(3n+c)=S$

By trial and error, one possible set of $n=5$ is

$$\begin{array}{|c|c|c|c|c|c|} \hline a & 0 & 1 & 2 & 3 & 4 \\ \hline b & 0 & 1 & 2 & -2 & -1 \\ \hline c & 0 & -2 & -4 & -1 & -3 \\ \hline \end{array}$$

That is, $$\begin{array}{|c|c|c|c|c|c|} \hline p & 1 & 2 & 3 & 4 & 5 \\ \hline q & 8 & 9 & 10 & 6 & 7 \\ \hline r & 15 & 13 & 11 & 14 & 12 \\ \hline \end{array}$$

Also see the links of similar question and magic rectangle

Snapshots one, two and three from Thomas R. Hagedorn, Magic rectangles revisited, Discrete Mathematics 207 (1999), 65-72.

• In fact, $n=1$ does not work and is excluded by the problem statement. You have not solved the general case, but you can extend this to the general case. – Ross Millikan Feb 28 '16 at 15:44
• @RossMillikan I've already mentioned it is trivial for $n=1$. Have you ever heard trivial solution? For example in math.stackexchange.com/questions/1396126/…. Actually the more general case appears in the links. Please spend your precious time to read it, it's wonderful. – Ng Chung Tak Feb 28 '16 at 15:57

Proof for partiton of {1,2,3,⋯,3n} = 3 different subset, we use n = 5 and n = 7
(Step 1)The basis (base case):
prove that the statement holds for the first natural number n. Usually, n = 0 or n = 1, rarely, n = –1 (although not a natural number, the extension of the natural numbers to –1 is still a well-ordered set).
(Step 2) The inductive step:
prove that, if the statement holds for some natural number n, then the statement holds for n + 2.
(n + 1) is not appliable since he want odd number["every odd n (n≥3)"]) Using Mathematical Induction(MI)

From the "example":
For n=3,

{3,5,7},{2,4,9},{1,6,8}


Then the sum will be {15},{15},{15} which then pass the logic "where each one has 3 elements and equal sum"

For n = 5,
we got up to: 3n = 3x5 = 15 :

1+2+3+...+15=120
120/n=24
24/3=8 (average of 3 number)

{1,8,15}{4,6,14}{2,9,13}{5,7,12}{3,10,11}


Sum of the five subnets are 24,24,24,24,24.
For n = 7,
we got up to: 3n = 3x7 = 21

1+2+3+...+21=231
231/n=33
33/3=11 (average of 3 number)

{1,14,18}{2,15,16}{3,13,17}{4,9,20}{5,7,21}{6,8,19}{10,11,12}


Sum of the seven subnets are 33,33,33,33,33,33,33.

ps I am not really sure this is correct or not coz i study this kind of mathematics in other language which i may make a mistake on that. Sorry for 1999.

• you havent understood the question clearly, it says equal sums – Abr001am Feb 28 '16 at 10:29
• awwww....I see his example of that have a different sum as 14,15,16... – phidias0303 Feb 28 '16 at 10:45
• this is not what is asked for plz reread the content of the question – Abr001am Feb 28 '16 at 11:33
• i sollicit you to comprehend what is demanded within the core of question, it says for each set of $3n$ find $n$ subsets – Abr001am Feb 28 '16 at 14:01
• You have shown solutions for $n=3,5,7$, but not how to extend them to the general case. – Ross Millikan Feb 28 '16 at 15:45