jump to navigation

Set and Subset Solution ខែ​មេសា 2, 2009

Posted 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)


Fill in your details below or click an icon to log in:

ឡូហ្កូ WordPress.com

អ្នក​កំពុង​បញ្ចេញ​មតិ​ដោយ​ប្រើ​គណនី WordPress.com របស់​អ្នក​។ Log Out / ផ្លាស់ប្តូរ )

រូប Twitter

អ្នក​កំពុង​បញ្ចេញ​មតិ​ដោយ​ប្រើ​គណនី Twitter របស់​អ្នក​។ Log Out / ផ្លាស់ប្តូរ )

រូបថត Facebook

អ្នក​កំពុង​បញ្ចេញ​មតិ​ដោយ​ប្រើ​គណនី Facebook របស់​អ្នក​។ Log Out / ផ្លាស់ប្តូរ )

Google+ photo

អ្នក​កំពុង​បញ្ចេញ​មតិ​ដោយ​ប្រើ​គណនី Google+ របស់​អ្នក​។ Log Out / ផ្លាស់ប្តូរ )

កំពុង​ភ្ជាប់​ទៅ​កាន់ %s

%d bloggers like this: