# Partitioning a Set so that the Sum is the Same

Let $M = \{1, 2, \dots , n\}$. What would be necessary and sufficient condition(s) for the number $m$, so that $M$ can be expressed as the disjoint union of $m$ subsets $A_i$, $(i = 1, 2, \dots, m$), such that

(i) each $A_i$ contains the same number of elements, and

(ii) the sum of all elements of $A_i$ is the same for $i = 1, 2, \ldots, m.$

Obviously, $m\mid n$. Other than that, I don't know where to begin!

-
Well another rather trivial necessary condition is that $m\mid \frac{n(n+1)}{2}$ –  EuYu Aug 27 '12 at 23:55

Since by (ii), the sum of the elements of $A_i$ is the same for every $i$, let's call this sum $S$.

1. Now we have $m$ sets each of which has elements that add up to $S$. That means that all together they add up to...?

2. But the sets are all disjoint, and together they contain all the elements of $M$, which is $\{1,2,\ldots,n\}$, so the sum of all of them together is the same as the sum of the elements of $M$, which is...?

3. But both (1) and (2) are two different ways of adding up the same thing, namely all the elements of the $A_i$, so those two sums must be equal, which gives you an equation, which is ...?

4. Each of the $A_i$ has the same number of elements. Say this number is $e$. Then since all together the $A_i$ have the sane number of elements as $M$ does, we can relate $e$ and $n$ and $m$ with the equation...?

I hope this gives you some ideas about where to begin.

An important principle at work here, which your class may not have pointed out, is that often there is some important piece of information, such as the number of elements in an $A_i$, or the sum of those elements, which doesn't have a name. If you can identify these important components, and name them, you are making progress.

-
Do you have any idea if the above conditions is sufficient for the partition? It is certainly necessary... –  EuYu Aug 28 '12 at 1:06
So these four facts tell us that $m,S|\frac{n(n+1)}{2}$ (more specifically $mS=\frac{n(n+1)}{2}$ , and $e|n$ (more specifically $em=n$). This seems to be a start, but I hardly think this can be the whole sufficient condition. Although your idea of introducing new variables is probably relevant, it seems we need to find more relationships between them now so we can trim our final answer to only $m$ and $n$. –  Raj Raina Aug 28 '12 at 4:30
BTW, the motivation behind this generalized question is a weaker question I came across, which said to prove such a partitioning holds when $n=1989$ and $m=17$ AND $m=117$... if that yields any insight –  Raj Raina Aug 28 '12 at 4:34
I wonder if these collection of constraints is also sufficient –  Belgi Aug 28 '12 at 21:52
@Raj I did not mean to suggest that it was the whole sufficient condition. You indicated that this was a homework problem, so I did not want to tell you the whole answer. You also said that you did not know how to start, so I gave you some information to start you off. Most schools have a policy that students are supposed to solve their own homework problems, not acquire solutions elsewhere, and I felt sure that you would not want to violate your own school's policy in this matter. I hope my answer was helpful. –  MJD Aug 28 '12 at 21:59