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.
Best Answer
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.