Go back
Subsets

Subsets

Posers and Puzzles

Vote Up
Vote Down

Seems therere quite a few mathappreciative people here.
So here is quite elegant problem for them.

Proove that every set ot ten different numbers (chosen from ste {1,2,...,100}) contains two disjoint nonempty subsets of the same sum.

Good luck,
madoldman.

Vote Up
Vote Down

Let A be a subset of {1,2,...,100} of size 10. Then A has 1022 proper subsets (ie ones which aren't A or empty), and given a proper subset, the sum of its elements must be a positive integer, bounded above by 100*9 = 900. So by the pigeon-hole principle we can find distinct proper subsets B and C with Sum(B) = Sum(C)

B cannot be a subset of C, because if it was, then Sum(C) >= Sum(B) + x for some x>0 in C\B, so Sum(C) > Sum(B); similarly B doesn't contain C. Hence the sets B\C and C\B are nonempty.
Sum(B\C) = Sum(B) - Sum(BnC) = Sum(C) - Sum(CnB) = Sum(C\B)

Therefore B\C and C\B are disjoint nonempty subsets of A with the same sum.

Vote Up
Vote Down

Very clean job, Acolyte!

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.