11
$\begingroup$

Let $A = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$.How many ways are there to partition this set into at least 2 subsets so the sum of the numbers in each subset is equal?

Here's what I've tried: Let $n$ be the number of subsets and $s$ the sum of the numbers in a subset(Where all the sets are equal). Since $n\cdot{}s=45$, $n$ has to divide $45$ and on the other hand, $s$ can't be smaller than $9$ so the only options for $n$ are $3$ and $5$. Now I know I can just count how many possible solutions there are given the fact that $n$ has only $2$ possible values but I was wondering is there a more elegant solution?

P.S: This actually came in a math contest and I didn't have time to count all the possible solutions so if there aren't any "better" solution, what do you think I should have done since I only had around $5$ minutes for this question.

$\endgroup$
  • 1
    $\begingroup$ This may be cheating :) but may I ask: what is the level of the math contest? If it's highschool level perhaps you're just supposed to count this in $5$ minutes, which seems tedious but just barely doable. The $n=5$ case is easy to count -- there's only one way to partition the positive numbers and then the $0$ can go with any of the $5$ sets, so there are $5$ ways total. The $n=3$ case seems tedious but doable in five minutes. $\endgroup$ – antkam May 17 at 20:49
  • $\begingroup$ @antkam It's high school level actually. But I really dislike these types of questions; they can be easily solved by computers in a matter of milliseconds and brute force is truly the only way to solve them. A math question should have an elegant solution and not something that could be easily done using brute force. $\endgroup$ – Borna Ghahnoosh May 17 at 22:03
  • 1
    $\begingroup$ While I mostly agree with your sentiment, there are good ways to count (e.g. the accepted Answer) and messy / error-prone ways to count, and one can argue the ability to find a clear, efficient, less error-prone way to count is a math skill. Imagine this is a programming exercise: then clearly some algorithms are better than others, right? Here you're just asked to run algorithm on paper... $\endgroup$ – antkam May 17 at 22:12
  • 3
    $\begingroup$ Anyway, you seem interested in the general problem, so you might enjoy knowing this: with general ground set $A$, the problem is (a generalization of) something called subset-sum and is NP-hard. $\endgroup$ – antkam May 17 at 22:12
9
$\begingroup$

Here is the tedious method that @antkam mentioned:

Consider the sums adding to 9. You have:

The set that contains $9$. The set that contains $8$ must contain $1$. The set that contains $7$ must contain $2$. The set that contains $6$ must contain $3$ (Because it cannot contain $1$ and $2$, which are already used). The set that contains $5$ must contain $4$ (Because $1, 3$ are both used). There is but one way to distribute the numbers $1$ through $9$. All that is left is to choose where to put $0$. For that, there are $5$ ways (Any set can have $0$ in it).

Next, consider when the sum is $15$ ($3$ sets). We want to consider the most restrictive numbers first (As this will eliminate possibilities the fastest): Let's write out all possible ways of summing to $15$ that contain a $9$ in non-zero digits:

$1+2+3+9, 1+5+9, 2+4+9, 6+9$

Next, do the same for $8$:

$1+2+4+8, 1+6+8, 2+5+8, 3+4+8, 7+8$

We only need to pick the first two sets (one set containing 9, one set containing 8). The rest of the digits will be in the third set. And, we can place the zero into any of the three sets, so every valid partition of the nonzero elements can be turned into three distinct partitions when we add in the zero.

$\{1,2,3,9\}$ can only pair with $\{7,8\}$: $3$ ways

$\{1,5,9\}$ can pair with $\{3,4,8\}$ or $\{7,8\}$: $6$ ways

$\{2,4,9\}$ can pair with $\{1,6,8\}$ or $\{7,8\}$: $6$ ways

$\{6,9\}$ can pair with $\{1,2,4,8\}$, $\{2,5,8\}$, $\{3,4,8\}$, or $\{7,8\}$: $12$ ways

Adding it all up, that is $5+3+6+6+12=32$ ways.

$\endgroup$
6
$\begingroup$

I think the key is understanding that $0$ can go wherever and that every number must go somewhere. Set aside $0$ for the moment.

When $n=5$ we have $s=9$. We can use an inductive reasoning as follows:

  • $9$ must be alone, so we get $\{9\}$ and that leaves $\{1,2,3,4,5,6,7,8\}$.
  • $8$ can only be paired with $1$ to reach $s=9$, so we get $\{1,8\}$ and that leaves $\{2,3,4,5,6,7\}$.
  • $7$ can only be paired with $2$ to reach $s = 9$, so we get $\{2,7\}$ and that leaves $\{3,4,5,6\}$.
  • Proceeding in this manner, we find that the subsets look like $\big\{\{9\}, \{1,8\}, \{2,7\}, \{3,6\}, \{4,5\}\big\}$.

All that remains is to assign $0$ to some subset, so we get $5$ possibilities for $s=9$.


When $n=3$ we have $s=15$ and things get slightly more complicated. We are still setting $0$ aside for this.

First, notice that $9$ and $8$ must go towards different subsets. We will then find how to fill up the $9$ subset, and for each such manner, we'll find out how to fill up the $8$ subset. The remaining numbers will form their own subset.

The idea behind this is that starting from the larger number is better because the remaining sum is smaller, so there are fewer options to consider.

So, we have $\{1,2,3,4,5,6,7\}$ and we have to figure out in how many ways we can pick elements from it to reach a sum of $6$. Now, proceeding as before, we find that the possibilities are $\big\{\{6\}, \{1,5\}, \{2,4\}, \{1,2,3\}\big\}$.

  • If the $9$ susbset is $\{6,9\}$, we are left with $\{1,2,3,4,5,7\}$ and we have to figure out in how many ways we can pick elements from it to reach a sum of $7$ (in order to complete the $8$ subset). We proceed as before and arrive at $\big\{\{7\}, \{2,5\}, \{3,4\}, \{1,2,4\}\big\}$. This gives us $4$ additional possibilities before adding $0$.

  • If the $9$ susbset is $\{1,5,9\}$, we are left with $\{2,3,4,6,7\}$ and we have to figure out in how many we can pick elements from it to reach a sum of $7$. We proceed as before and arrive at $\big\{\{7\}, \{3,4\}\big\}$. This gives us $2$ additional possibilities before adding $0$.

  • If the $9$ susbset is $\{2,4,9\}$, we are left with $\{1,3,5,6,7\}$ and we have to figure out in how many we can pick elements from it to reach a sum of $7$. We proceed as before and arrive at $\big\{\{7\}, \{1,6\}\big\}$. This gives us $2$ additional possibilities before adding $0$.

  • Finally if the $9$ susbset is $\{1,2,3,9\}$, we are left with $\{4,5,6,7\}$ and we have to figure out in how many we can pick elements from it to reach a sum of $7$. Clearly, the only way is picking a lone $7$ which gives us $1$ additional possibility before adding $0$.

So we have $9$ possibilities without $0$. For each such configuration, we have $3$ ways to assign $0$ to a subset, which gives us $9\times 3 = 27$ total possibilities in the $n=3$ case.


In total, this gives us $27+5 = 32$ possibilities.


Now, this is a structured way of thinking to approach this problem (tackle the large numbers to reduce leftover sum possibilities), but there is of course a more... operational approach. Generating functions are a handy tool for any combinatorist to have.

One way to consider this problem if you have computational power at hand is as follows.

When $n=3$, we consider the product

$$\prod_{i=0}^9 (x_1^i+x_2^i+x_3^i).\tag{$*$}$$

Expanding this product, we'll find a sum of monomials of the form $c\cdot x_1^ax_2^bx_3^c$. Each such monomial can be interpreted as follows: there are $c$ ways to partition the set $\{0,1,2,\dots,9\}$ such that the first subset sums to $a$, the second subset sums to $b$ and the third subset sums to $c$.

Indeed, when expanding the product, at each step we must choose which $x_i^j$ we're taking. Choosing $x_i^j$ means assigning the element $j$ from $\{0,1,2,\dots,9\}$ to the $i$-th subset.

Since we want all our subsets to sum to $s=15$, we're then interested in the coefficient of $x_1^{15}x_2^{15}x_3^{15}$ in the expansion of $(*)$. Of course, since we also don't care about the order of our subsets, we have to divide the end result by $3!$.

When I say we don't care about the order of our subsets, I mean that the family of subsets $\big\{\{0,6,9\}, \{7,8\}, \{1,2,3,4,5\}\big\}$ is just as good as $\big\{\{7,8\}, \{1,2,3,4,5\}, \{0,6,9\}\big\}$ or any other permutation.

You can check with Wolfram Online Notebooks (or your choice of math software) using 1/3! * Coefficient[Product[(x^i+y^i+z^i),{i,0,9}], x*y*z,15] that the answer comes out to $27$, like we did when counting by hand.

Similarly, to count the number of possibilities for $n=5$ we'd look at

$$\frac1{5!}\left[x_1^9x_2^9x_3^9x_4^9x_5^9\right]\left(\prod_{i=0}^9 (x_1^i+x_2^i+x_3^i+x_4^i+x_5^i)\right).$$

You can check with 1/5! * Coefficient[Product[(a^i+b^i+c^i+d^i+e^i),{i,0,9}], a*b*c*d*e, 9] that the answer comes out to $5$, like we did when counting by hand.

I will say, however, that this is not a computationally cheap or fast way to obtain the answer (if you are interested in computationally feasible ways to approach this problem, it is traditionally handled with a technique called dynamic programming). So, if you can afford to let the computer do the calculations for you while you're doing something else, go ahead. Of course, you can also expand the product by hand yourself if you prefer.

You can also combine both methods. This approach clearly suffers at higher values of $n$, because the number of monomials in the product expansion grows too fast with $n$. On the other hand, for higher values of $n$, $s$ is lower and we see from the example that the inductive reasoning becomes simpler, with less combinations to consider.

Finally, this approach also tackles other variations of this problem, like specifying different sums for different subsets and also generalizing to ordered subsets.

$\endgroup$
  • $\begingroup$ I wonder if symmetric polynomial theory would be of any help here. It doesn’t seem to simplify things all that much though... $\endgroup$ – Roman Odaisky May 18 at 0:38
  • $\begingroup$ +1 despite being not useful in a math contest :) this is a great answer to OP's request for "elegance". $\endgroup$ – antkam May 18 at 1:32

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.