For which integers $n>1$ is there a set of positive integers $S\subseteq \mathbb{N}$ with $n$ elements, and for every $s\in S$ the set $S\setminus\{s\}$ can be partitioned into two subsets with equal sum?



Finite subsets of $S\subseteq \mathbb{N}$ such that $S\setminus\{s\}$ can be partitioned with equal sum
As conjectured by bof, the answer is all odd $n \geq 7$.


*Proof.* Let $S$ be a set of positive integers such that $S \setminus \{s\}$ can be partitioned into two sets of equal sum for all $s \in S$. By parity considerations, note that all elements of $S$ are either all odd or all even. If all elements of $S$ are even, then the set obtained from $S$ by dividing every element by $2$ is also a valid set. Repeating this argument, we may assume that all elements of $S$ are odd. This implies that $n$ must be odd. Clearly, $n \notin \{1,3\}$ and bof has shown $n=5$ is also impossible (see comment below). To complete the proof we now show that every odd $n \geq 7$ is possible.


As noted by bof, $S=\{1,3,5,7,9,11,13\}$ shows that $n=7$ is possible, and it is easy to check $S=\{1,3,5,7,9,11,13,15,17\}$ is also valid. We will show by strong induction on $k$ that $S=\{1,3, \dots, 4k+1\}$ is a valid set. If $s \in \{1, 3, \dots, 4k-7\}$, then $\{1, 3, \dots, 4k-7\} \setminus \{s\}$, can be partitioned into two equal sum sets by induction. Since $\{4k-5, 4k-3, 4k-1, 4k+1\}$ can also be partitioned into two equal sum sets, we are done. If $s \in \{4k-5, 4k-3\}$, then by induction $\{1, 3, \dots, 4k-3\} \setminus \{s\}$ can be partitioned into two equal sum sets $S\_1$ and $S\_2$. Suppose that $1 \in S\_1$. Then $(S\_1 \setminus \{1\}) \cup \{4k+1\}$ and $S\_2 \cup \{1, 4k-1\}$ are equal sum subsets of $S \setminus \{s\}$. Suppose $s=4k-1$. By induction, there is a partition of $\{1, 3, \dots, 4k-5\}$ into two equal sum sets $S\_1$ and $S\_2$. Suppose $4k-5 \in S\_1$, Then there must be some $\ell \in S\_1$ such that $\ell-2 \in S\_2$. We obtain the required partition of $S \setminus \{s\}$ by swapping $\ell$ and $\ell-2$, adding $4k+1$ to $S\_1$, and adding $4k-3$ to $S\_2$. Finally, suppose $s=4k+1$. By induction, there is a partition of $\{1, 3, \dots, 4k-7\} \cup \{4k-3\}$ into two equal sum sets $S\_1$ and $S\_2$. Suppose $4k-7 \in S\_1$. Then there must be some $\ell \in S\_1$ such that $\ell-2 \in S\_2$. The required partition of $S \setminus \{4k+1\}$ is obtained by swapping $\ell$ and $\ell-2$, adding $4k-1$ to $S\_1$, and adding $4k-5$ to $S\_2$.


