# Prove that any $6$- subset of integers $\{1…14\}$ is always the union of two distinct subsets of equal sum

We start with a 6-element subset $A$ of $\{1,\dots ,14\}$. What we'd like to prove is that there always exist two subsets of $A$, $A_1$ and $A_2$ such that: $$A_1 \cup A_2 = A$$ $$A_1 \neq A_2$$ $$\sum_{k\in A_1} k = \sum_{k \in A_2} k$$ That is, we want to split $A$ into two sets, possibly overlapping, whose sum of elements is equal.

I know this proof smells like pigeonhole principle, but how do I approach it? Furthermore how could I generalize it to k-element subsets of $\{1, \dots ,n\}$? When is it possible and when not?

• I'm sorry, I must have worded it poorly. What we start with is set of 6 numbers about which we know only that they have been taken from the set $\{1\dots 14\}$. What we want to do is to prove that no matter which 6 elements were chosen we can further split the set according to the conditions given above. – MeyCJey May 1 '18 at 19:59
• split is not the correct word – Yorch May 1 '18 at 20:05
• I think you did not post the problem clearly. What if you take a subset only consisting of one element? Then either A1 or A2 is empty. What if A is the subset consisting of 1 and 2? – tommsch May 1 '18 at 20:10
• $A$ has $6$ elements – Yorch May 1 '18 at 20:11
• @Jorge I know, but I couldn't think of a better one. Is there perhaps a mathematical term for this pseudo-partition, where we relax the pairwise-disjoint condition? – MeyCJey May 1 '18 at 20:22

There are $2^6-2=62$ non trivial subsets of a subset of cardinality $6$. Each of these subsets will have a sum of elements between $1$ and $14+13+12+11+10=60$. So two of these subsets must have a sum that is equal.
• I think you also need to use the fact that u can join them with $A\setminus(A_1\cup A_2)$ so they indeed cover everything – Yorch May 1 '18 at 20:08