5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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\}$. $\endgroup$ – Anurag A Feb 28 '16 at 8:42
  • 1
    $\begingroup$ For $n=3$, either rows or columns of $3\times 3$ magic square will do. $\endgroup$ – Ng Chung Tak Feb 28 '16 at 9:58
5
$\begingroup$

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$

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Feb 28 '16 at 15:44
  • 1
    $\begingroup$ @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. $\endgroup$ – Ng Chung Tak Feb 28 '16 at 15:57
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.