Sets and SubsetsDate: 03/11/2003 at 12:04:28 From: Erkan Melih Sensoy Subject: Sets and subsets Consider a collection of 26 stones weighted 1, 2, 3, … , 26 grams. Let us denote it by A(26). Prove that any subset C of A(26) consisting of at least 7 stones contains two separate subsets with equal total weights. Date: 03/12/2003 at 08:34:00 From: Doctor Jacques Subject: Re: Sets and subsets Hi, It is enough to consider subsets of exactly 7 stones (if there are more, we just ignore the others). If the subset C contains {23, 24, 25, 26}, we have: (23 + 26) = (24 + 25) and we are done. Otherwise, the weight of any subset of C of at most 4 elements will between 1 and: (23 + 24 + 25 + 26) - 1 = 97 i.e. that weight can take at most 97 values. Let us count the number of subsets of at most 4 elements. The number of subsets of k elements is: C(7,k) = 7! / (k! * (7-k)!) If we compute these values for k = 1, .. 4, we get: k C(7,k) ------------- 1 7 2 21 3 35 4 35 for a total of 98. This means that we have 98 different non-empty subsets that can take at most 97 different values. Can you continue from here? Please feel free to write back if you want further help. - Doctor Jacques, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/