Question

Number of non-empty subsets of $\{1, 2, 3, ...,12\}$ having the property that sum of the largest and smallest element is 13.

Answer 1

1365

Answer 2

Let the given set be $S = \{1, 2, 3, ..., 12\}$. We are looking for the number of non-empty subsets $A \subseteq S$ such that the sum of the largest and smallest element in $A$ is 13. Let $a = \min(A)$ and $b = \max(A)$. The conditions are:

1. $A$ is non-empty.
2. $a, b \in S$.
3. $a < b$ (since $a$ is the smallest and $b$ is the largest, they must be distinct if the subset has more than one element. If $A=\{k\}$, then $a=b=k$, so $2k=13$, $k=6.5$, not possible. Thus, any valid subset must have at least two elements, ensuring $a < b$).
4. $a + b = 13$.

We need to find pairs of elements $(a, b)$ from $S$ that satisfy $a + b = 13$ and $a < b$. The possible pairs are:

• If $a=1$, then $b=12$. Pair: $(1, 12)$.
• If $a=2$, then $b=11$. Pair: $(2, 11)$.
• If $a=3$, then $b=10$. Pair: $(3, 10)$.
• If $a=4$, then $b=9$. Pair: $(4, 9)$.
• If $a=5$, then $b=8$. Pair: $(5, 8)$.
• If $a=6$, then $b=7$. Pair: $(6, 7)$.

For each such pair $(a, b)$, the subset $A$ must contain $a$ and $b$. The other elements of $A$ can be any subset of the elements in $S$ that lie strictly between $a$ and $b$. This intermediate set is $\{a+1, a+2, ..., b-1\}$.

The number of elements in this intermediate set is $(b-1) - (a+1) + 1 = b - a - 1$. The number of subsets that can be formed from these intermediate elements is $2^{b-a-1}$. Each of these subsets, when combined with $\{a, b\}$, forms a valid subset $A$.

Let's calculate the number of subsets for each pair:

1. Pair (1, 12): $a=1, b=12$. Intermediate set: $\{2, 3, ..., 11\}$. Number of elements = $12 - 1 - 1 = 10$. Number of subsets = $2^{10} = 1024$.
2. Pair (2, 11): $a=2, b=11$. Intermediate set: $\{3, 4, ..., 10\}$. Number of elements = $11 - 2 - 1 = 8$. Number of subsets = $2^8 = 256$.
3. Pair (3, 10): $a=3, b=10$. Intermediate set: $\{4, 5, ..., 9\}$. Number of elements = $10 - 3 - 1 = 6$. Number of subsets = $2^6 = 64$.
4. Pair (4, 9): $a=4, b=9$. Intermediate set: $\{5, 6, ..., 8\}$. Number of elements = $9 - 4 - 1 = 4$. Number of subsets = $2^4 = 16$.
5. Pair (5, 8): $a=5, b=8$. Intermediate set: $\{6, 7\}$. Number of elements = $8 - 5 - 1 = 2$. Number of subsets = $2^2 = 4$.
6. Pair (6, 7): $a=6, b=7$. Intermediate set: $\emptyset$. Number of elements = $7 - 6 - 1 = 0$. Number of subsets = $2^0 = 1$.

The total number of such non-empty subsets is the sum of the counts from all possible pairs: Total = $2^{10} + 2^8 + 2^6 + 2^4 + 2^2 + 2^0 = 1024 + 256 + 64 + 16 + 4 + 1 = 1365$.

This is a geometric series with the first term $c = 2^0 = 1$, the common ratio $r = 2^2 = 4$, and the number of terms $n = 6$. The sum of a geometric series is given by $S_n = c \frac{r^n - 1}{r - 1}$. Sum = $1 \times \frac{4^6 - 1}{4 - 1} = \frac{(2^2)^6 - 1}{3} = \frac{2^{12} - 1}{3} = \frac{4096 - 1}{3} = \frac{4095}{3} = 1365$.

All subsets formed this way are guaranteed to be non-empty because each subset includes at least the minimum and maximum elements ($a$ and $b$), which are distinct.