I am confused why there are $2^{10}$ (1024 subsets of distinct 10 digit natural numbers) Can someone please explain?

Reference : pigeonhole principle problem :

Prove that from a set of ten distinct two-digit natural numbers, it is possible to select two disjoint nonempty subsets whose members have the same sum. Outline. There are $2^{10}$ = 1024 subsets of a ten element set, but the sum of the numbers in any subset is a non-negative integer less than 1000.

  • $\begingroup$ Any $10$ element set has $2^{10}$ subsets. For line up the elements in a row. We are making a subset. We can decide whether or not to include the first object, $2$ choices. For every choice we have made, there are $2$ ways to decide about the second object. So there are $2^2$ ways to decide about the first two objects. For each of thse, there are $2$ ways to decide about the third object, and so on. $\endgroup$ – André Nicolas Aug 19 '14 at 4:25

You want to select two disjoint nonempty subsets, as stated in the problem. Since the subsets are disjoint, that means that no element of the original set can go in both subsets, it either goes in subset 1 or subset 2.

Each of the $10$ elements (the two-digit numbers you have) therefore has two possible choices, so trivially we know that this would be $2^{10} = 1024$ possible ways to form the two disjoint subsets.

  • $\begingroup$ The details depend on whether one is choosing ordered pairs of disjoint subsets, or unordered pairs. Whichever one decides, for large $n$ the number of ways is greater than $2^n$. But for single subsets, which OP asked about, it is $2^n$. $\endgroup$ – André Nicolas Aug 19 '14 at 4:36

Consider adding up all the sets of 0 elements, 1 element, 2 elements, 3 elements and so forth. Each of these can be done in "10 choose x" ways where x is the number of elements which could be totaled as the binomial expansion of $(1+1)^{10}$ for another way to look at this.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.