All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Subsetting a set (Posted on 2004-06-29)
Out of the set {1,2,3...100} take any subset of ten numbers and call it T. Prove you can find two disjoint subsets of T such as the sum of the numbers in each subset is the same.

Note: the subsets need not include every number in T; in fact, if you asked for this condition, the problem might be impossible (prove it!).

 See The Solution Submitted by Federico Kereki Rating: 3.8000 (5 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution 1st part | Comment 4 of 9 |
There are 2^10 subsets of the chosen set of 10.  This is 1024, but one of them is the null set, so there are really only 1023 sets. The highest total of any subset of 10 is 100+99+...+91 = 955, so some different (distinct) subsets must share the same total.  If these subsets are not disjoint, just remove the elements (numbers) they have in common, and they will still add to the same total.
 Posted by Charlie on 2004-06-29 14:24:46

 Search: Search body:
Forums (0)