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/