# Set of ten distinct two-digit natural numbers

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.

• 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. – André Nicolas Aug 19 '14 at 4:25

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.
• 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$. – 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.