perplexus.info :: Numbers : Subsetting a set

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!).

Submitted by Federico Kereki

Rating: 3.8000 (5 votes)

Solution: (Hide)

Out of 10 numbers, there are 1023 ways of picking subsets. However, with 10 numbers out of T, the minimum sum is 1, and the maximum sum is 955 (=91+92+...+99+100). As there are more subsets than possible sums, there must be at least two subsets with the same sum. [Note: if the two subsets with the same sum have common elements, just remove them and you'll get disjoint sets, with still the same sum.]
For the second question: If T had ONE odd number and NINE even numbers, and the union of both subsets had to be T, then the sum of the numbers in one of the subsets would be odd, and the other sum would be even.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
Second part (again)	Erik O.	2004-06-29 16:00:01
re(3): solution 1st part	Richard	2004-06-29 14:47:08
re(3): Second part	Nick Hobson	2004-06-29 14:44:03
re(2): solution 1st part	SilverKnight	2004-06-29 14:42:34
re: solution 1st part	Richard	2004-06-29 14:35:37
solution 1st part	Charlie	2004-06-29 14:24:46
re(2): Second part	Charlie	2004-06-29 14:19:40
re: Second part	Nick Hobson	2004-06-29 14:11:34
Second part	Oskar	2004-06-29 13:59:41

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (19)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info