In: Advanced Math
Discrete math : Show your work please.
Consider a set X of 10 positive integers, none of which is greater than 100. Show that it has two distinct subsets whose elements have the same sum.
let a set x of 10 positive integers will be two digits. now
claim that it has two distinct subsets whose elements have the same
sum. Note that there are distinct subsets of our set of
10 two-digit numbers. Also note that the sum of the elements of any
subset of our set of 10 two-digit numbers must be between 10 and
, which is less than
. There are even less attainable
sums. The Pigeonhole Principle then implies that there are two
distinct subsets whose members have the same sum. Let these sets be
and
. Note that
and
are two distinct sets whose
members have the same sum. These two sets are subsets of our set of
10 distinct two-digit numbers, so this proves the claim.