Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Sets and Subsets

Date: 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 

Date: 03/12/2003 at 08:34:00
From: Doctor Jacques
Subject: Re: Sets and subsets


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
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.