Two subset with equal sum

For students of class 11-12 (age 16+)
User avatar
Moon
Site Admin
Posts: 751
Joined: Tue Nov 02, 2010 7:52 pm
Location: Dhaka, Bangladesh
Contact:

Two subset with equal sum

Unread post by Moon » Tue Dec 14, 2010 12:21 am

Given any set of $10$ natural numbers between $1$ and $99$ inclusive, prove that there are two disjoint nonempty subsets of the set with equal sums of their elements.
"Inspiration is needed in geometry, just as much as in poetry." -- Aleksandr Pushkin

Please install LaTeX fonts in your PC for better looking equations,
learn how to write equations, and don't forget to read Forum Guide and Rules.

Navedimtiaz
Posts: 3
Joined: Thu Dec 16, 2010 2:06 pm

Re: Two subset with equal sum

Unread post by Navedimtiaz » Thu Dec 16, 2010 2:21 pm

The highest sum of a subset here is 945(=90+91+92+93+94+95+96+97+98+99)
So the sum ranges from 1 to 945.
the number of subset is 1023(=2^10-1)
1023 subsets,945 sums,pigeonhole,..........................thats it \m/

Navedimtiaz
Posts: 3
Joined: Thu Dec 16, 2010 2:06 pm

Re: Two subset with equal sum

Unread post by Navedimtiaz » Fri Dec 17, 2010 2:38 pm

forgot to write......Two set with same sum can have common elements.If they do,substract the sum of common elements from both sets and there will be two disjoint sets with same sum.If they don't,then the case is solved:):)

Post Reply