Discrete Math Let S be a set of 6 positive integers whose ma

(Discrete Math) Let S be a set of 6 positive integers whose maximum is at most 14. Show that the sums of the elements in all the non-empty subsets of S cannot all be distinct.

Solution

For each nonempty subset A of S the sum of the elements in A denoted

SASA

satisfies

1SA9+10+...+14=691SA9+10+...+14=69

and there are

261=63261=63

nonempty subsets of S. We should like to draw the conclusion from the pigeonhole principle by letting the possible sums, from 1 to 69 be the pigeonholes with 63 nonempty subsets of S as the pigeons but then we have too few pigeons.

In this example you are putting the subsets of SS (which all have sums) and placing them into the sums of 11 to 6969. Think of the sums of SS as bins, we only have 6363 non empty subsets, and 6969 bins to put them in.