# If a set of integers can be partitioned into 3 subsets with equal sums, if one such subset is identified, can the remaining be partitioned as well?

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.

• I wonder if your feeling is correct if you require each subset to contain one third of the elements. – Ethan Bolker Jan 4 '16 at 0:47
• @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. – JMoravitz Jan 4 '16 at 0:56
• @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. – JMoravitz Jan 4 '16 at 1:00
• @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. – Ethan Bolker Jan 4 '16 at 1:14

$\{1,3,4,5,8,14,16\}$
$\{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.