Set and Subset Solution ខែមេសា 2, 2009Posted by psvjupiter in គណិតវិទ្យា.
The number of subset that S can have is 2^8=256 subset.
Suppose sum1, sum2, sum3,…, sum256 is the sum of all elements in each of those 256 subsets.
Then of course sum1, sum2, sum3,…, sum256 >=0 (ZERO) since the minimum sum is the empty subset which contain no elements.
Also The subset that has the maximum sum does not exceed 29+28+27+26+25+24+23+22=204
So we have 0<= sum1,sum2,sum3,……….., sum256 <=204
or put is simply those 256 number can only be from 0, 1, 2, 3, …..,204. (from 0 to 204 , 205 distinct numbers)
Then it is clear that at least 2 number must be the same. why? You have 256 numbers and the choice you can values these number is only 205 choices (see my explain more if doubt), so at least 2 must be the same. (Prove)
More explanation : suppose you value the sum1, sum2, sum3,…., sum 256 randomly 0 1 2 3… 204 in a way that once you assign one value from [0,204] to sum(i)ណាមួយ, you cross that number out from [0,204] so that each sum(i) are all diffrent. But that impossible. When eventually you have assign 204 to a sum(i) you have cross out all of number in range [0,204] already. So the remaing sum (j) must take the same value from [0, 204]…
(This is also called pigeon hole principle or dirichlet principle)