0
$\begingroup$

Given a positive integer $n$, we construct a multiset $S$ which contains only integers from $1$ to $n$, with each appearing at least once. Determine the values of $n$ for which any such set $S$ whose elements have an even sum can be partitioned into two subsets each with the same sum.

This is related to the Partition problem which is known to be NP-hard. Further, I'd be interested to know if there are any sufficient conditions for some multiset to be able to be partitioned into two subsets of equal sum. Some obvious necessary conditions include the sum being even, and the largest element being less than half the sum.

$\endgroup$
2
$\begingroup$

As long as $S$ contains each integer from $1$ to $n$ at least once and the sum is even, this is always possible.

Without loss of generality we can assume that $S$ contains each number either once or twice (any additional elements can simply be taken out in pairs and distributed evenly between the two partitions).

So what we need to find is a subset that sums to half of $\sum S$. But this half will always be at most $\sum_{k=1}^n k$, and it is easy to see that every number below this limit can be made by picking each number between $1$ and $n$ either once or not at all.

$\endgroup$

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.