Consider the set $A = \{1, 2, ..., n\}$, where $n \in N, n \ge 6$. Show that $A$ is the union of three pairwise disjoint sets, with the same cardinality and the same sum of their elements, if and only if $n$ is a multiple of $3$.
Problem
Source: Indian Postal Coaching 2008 set 6 p4
Tags: partition, combinatorics, Subsets
jelena_ivanchic
26.02.2021 14:17
Beautiful problem and I think the construction is really nice!
Clearly, because of the cardinality stuff, $n$ should be divisible by $3.$
Now we will show that for $n\ge 6$ and divisible there exist a construction [ Note in these constructions, $A, B, C$ denotes the three disjoint set ]
For $n=6,$ consider this construction
$$1^A~~2^B~~3^C$$$$4^C~~5^B~~6^A$$
And note that this construction can be used for any $6$ consecutive integers i.e for $k,k+1,k+2,k+3,k+4,k+5$ consider this:-
$$k^A~~~{k+1}^B~~{k+2}^C$$$${k+3}^C~~{k+4}^B~~{k+5}^A$$
And for $n=9,$ consider this
$$1^A~~2^B~~3^C$$$$4^C~~5^A~~6^B$$$$7^B~~8^C~~9^A$$
Now we are set for making the construction for any $n=3k, k>1.$
Now if $3k$ is even, then we can just repeat our construction for $n=6.$
[ like grouping them in consecutive $6$ integers i.e $(1-6),(7-12),\dots $]
And if $3k$ is odd, then consider $n=3k-9.$ Since $3k-9$ is even, we can do the construction, we did for even and then the last $9$ integers can be arranged in the $n=9$ construction.
And we are done!