Specifically, if a set $S$ of integers that sums to $k$ is known to be able to be partitioned into $3$ subsets such that each subset sums to $\dfrac{k}{3}$, if $A$ is one such subset of $S$, is it always possible to partition the remaining integers of $S-A$ into two subsets that both sum to $\dfrac{k}{3}$?

For example, if $S = \{2, 3, 4, 6, 7, 8\}$ and sums to $30$, it can be divided into sets $\{2, 8\}$, $\{3, 7\}$, and $\{4, 6\}$ which each sum to $\dfrac{30}{3}=10$. This is a simple example, but if an arbitrary set $S$ that sums to $k$ is known to be able to be partitioned into 3 subsets that each sum to $\dfrac{k}{3}$, if one such subset $A$ is identified, is it guaranteed that the remaining integers in $S-A$ can also be partitioned into subsets that each sum to $\dfrac{k}{3}$?

My gut feeling is that the answer is yes, but I don't know how to prove it.

  • $\begingroup$ I wonder if your feeling is correct if you require each subset to contain one third of the elements. $\endgroup$ – Ethan Bolker Jan 4 '16 at 0:47
  • $\begingroup$ @EthanBolker My intuition is that it could still fail. Even so, "containing one third of the elements" wouldn't make sense if the total number of elements wasn't a multiple of $3$ to begin with. The same tactic I used to construct the counterexample below should probably still hold. Have precisely three odd elements and the correct partition has exactly one odd element each, and find a subset of correct size and total using all odd elements. $\endgroup$ – JMoravitz Jan 4 '16 at 0:56
  • 1
    $\begingroup$ @EthanBolker Playing with it a moment found $\{1,3,5,4,0,8,-2,12,-4\}=\{0,4,5\}\cup \{3,8,-2\}\cup \{1,12,-4\}$. partitioned into subsets of size three each of whose sum is equal to $9$. $\{1,3,5\}$ is also a subset of size three whose sum is $9$. All remaining elements are even and could therefore not be partitioned into sets adding to $9$. If the fact that some are negative bothers you, then add four to every number, or five or more. $\endgroup$ – JMoravitz Jan 4 '16 at 1:00
  • $\begingroup$ @JMoravitz What if the set to partition is the interval $\{1, \ldots , 3n\}$? See arxiv.org/abs/1304.6756. published in Journal of Combinatorics (JOC) Vol. 7.1. $\endgroup$ – Ethan Bolker Jan 4 '16 at 1:14


can be partitioned into the sets

$\{1,16\},\{3,14\},\{4,5,8\}$, each of which add to $17$.

The subset $A=\{1,3,5,8\}$ is also a subset which adds to $17$, however the remaining integers $\{4,14,16\}$ are all even and therefore could not possibly be partitioned into subsets which add to an odd number.

  • 1
    $\begingroup$ I'm not surprised by many upvotes for this answer, but given that I am surprised at so few for the question. $\endgroup$ – Ethan Bolker Jan 4 '16 at 0:46

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.