1. PF Contest - Win "Conquering the Physics GRE" book! Click Here to Enter
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Using the method of mathematical induction

  1. Feb 7, 2010 #1

    1. The problem statement, all variables and given/known data
    Let H be a ten- element set of potive integers ranged from 1 to 99. Prove that H has two disjoint subsets A and B so that the sum of the elements of A is equal to the sum of the elements of B.
  2. jcsd
  3. Feb 7, 2010 #2
    I think this is most naturally a pigeonhole problem. Pigeonhole hint: there are 2^10 - 2 = 1022 non-empty proper subsets of H, the sum of the elements of any such subset lies in 1..1000 so can take on at most 1000 different values (in fact it's quite less than this, but this is a strong enough statement) which is less than 1022.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook