For which values of $n$ can the set $\{1,2,...,n\}$ be partitioned into three sets with the same sums of elements ?
E.g $\{1,2,3,4,5\}=\{1,4\}\cup \{2,3\}\cup \{5\}$ ;
$\{1,2,3,4,5,6\}=\{1,6\}\cup \{2,5\} \cup \{3,4\}.$
The following is one of the old contest problems (22nd All Soviet Union Math Contest, 1988).
Let $m,\; n,\; k$ be positive integers with $m \geqslant n$ and $1+2+\cdots +n=m\cdot k$. Prove that the numbers $1,\;2,\;\cdots,n$ can be divided into $k$ groups in such a way that the sum of the numbers in each group equals $m$.
CiP example: $1+2+3+4+5+6+7+8+9=45$;
from $45=9\cdot 5$ the partition of $k=5$ groups is obtained, each with a sum of $m=9$
$$\{1,\;8\}\cup \{2,\;7\}\cup\{3,\;6\}\cup \{4,\;5\}\cup\{9\};$$
from $45=15 \cdot 3$ the partition of $k=3$ goups is obtained, each with a sum of $m=15$.
$$\{1,\;2,\;3,\;9\} \cup \{4,\;5,\;6\} \cup \{7,\;8\}.$$
CiP exampl$e^{bis}$: $1+2+3+4+5+6+7+8=36=12 \cdot 3$ and we have the partition of $k=3$ subsets, with the sum of $m=12$
$$\{1,\;2,\;3,\;6\} \cup \{4,\;8\} \cup \{5,\;7\}.$$
It would seem that the answer to the original question is $n=3\cdot p-1$ or $n=3\cdot p$. That is, in the case of $n=3\cdot p+1$, there is no such partition. (Indeed, if $n=3\cdot p+1$, then, because $$1+2+ \cdots +n=\frac{n(n+1)}{2}=\frac{(3p+1)(3p+2)}{2}=9\cdot \frac{p(p+1)}{2}+1,$$ this sum should be a multiple of 3, which is not true.)
If $n=3p$ then $1+2+ \cdots +n=\frac{3p(3p+1)}{2}=3 \cdot \frac{p(3p+1)}{2}=3\cdot \frac{p(p+1+2p)}{2}=3\cdot m$,
and $p$ or $p+1$ is divisible by $2$ so $m$ is integer.
If $n=3p-1$ then $\frac{n(n+1)}{2}=\frac{(3p-1) p}{2}=\frac {(2p+p-1)\cdot p}{2}=3 \cdot m$
with $m$ integer by the same arguments.
So in these cases we fall over the general problem given to the 22nd All Soviet Union Math Contest, 1988.
Another example in the case of $n=15$ is here : math.stackexchange.com/questions/31929/partition-of-equal-size-and-equal-sum
The proof is given by induction, resulting in a way of constructing the partitions.
The general problem has an object if $n \geqslant 3$.
For $n=3$ we have only one partition $\{1,\;2\} \cup \{3\}.$
For $n=4$ such partitions do not exsist.
For $n=5,\;6$ are just the examples presented previously.
For $n=7$ such partitions do not exist.
For $n=8$, because $1+2+\cdots +8=36=9 \cdot 4=12 \cdot 3=18 \cdot 2$ we have in addition to the presented previously and the partitions
$$\{1,\;2,\;3,\;4,\;8\}\cup \{5,\;6,\;7\},\;\{1,\;3,\;6,\;8\}\cup \{2,\;4,\;5,\;7\}$$
$$\{1,\;4,\;5,\;8\}\cup \{2,\;3,\;6,\;7\}\;,\;\{1,\;4,\;6,\;7\}\cup \{2,\;3,\;5,\;8\}$$
$$\{1,\;2,\;4,\;5,\;6\}\cup \{3,\;7,\;8\}\;,\;\{1,\;2,\;3,\;5,\;7\} \cup \{4,\;6,\;8\}$$
$$\{1,\;2,\;7,\;8\}\cup \{3,\;4,\;5,\;6\}.$$
For $n=9$, because $1+2+\cdots+9=45=9\cdot 5=15 \cdot 3$ are just the examples presented previously.
Niciun comentariu:
Trimiteți un comentariu