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?

  • 1
    $\begingroup$ 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. $\endgroup$ – MeyCJey May 1 '18 at 19:59
  • $\begingroup$ split is not the correct word $\endgroup$ – Jorge Fernández Hidalgo May 1 '18 at 20:05
  • $\begingroup$ 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? $\endgroup$ – tommsch May 1 '18 at 20:10
  • $\begingroup$ $A$ has $6$ elements $\endgroup$ – Jorge Fernández Hidalgo May 1 '18 at 20:11
  • $\begingroup$ @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? $\endgroup$ – MeyCJey May 1 '18 at 20:22

You are right, the pigeon principle is key.

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.

  • 1
    $\begingroup$ 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 $\endgroup$ – Jorge Fernández Hidalgo May 1 '18 at 20:08

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.