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
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/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search