3
$\begingroup$

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!

  • 0
    Well another rather trivial necessary condition is that $m\mid \frac{n(n+1)}{2}$2012-08-27

1 Answers 1

2

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.

  • 0
    @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.2012-08-28