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.
Asked
Active
Viewed 432 times
5
-
2Your 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 08:42
-
1For $n=3$, either rows or columns of $3\times 3$ magic square will do. – Ng Chung Tak Feb 28 '16 at 09:58
2 Answers
5
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$
Ross Millikan
- 374,822
-
1
-
1
-
1@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
3
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.
Ng Chung Tak
- 18,990
-
1In 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
-
1@RossMillikan I've already mentioned it is trivial for $n=1$. Have you ever heard trivial solution? For example in http://math.stackexchange.com/questions/1396126/trivial-and-non-trivial-solution-of-homogeneous-equation. 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