TIFR CSE 2025 | Part A | Question: 15

Question

How many subsets of $\{1,2, \ldots, 2 n\}$ do not contain two numbers with sum $2 n+1?$

• A. $3^{n}+\binom{2 n}{2}$
• B. $3^{n}$
• C. $4^{n}-\binom{2 n}{2}$
• D. $2^{n}$
• E. None of the above

   

Answer 1

The pairs here that sum to \(2n + 1\) are:  
\[
(1, 2n), (2, 2n - 1), (3, 2n - 2), \dots, (n, n + 1)
\]

There are \(n\) such pairs, and each element of the set appears in exactly one pair.  
So these \(n\) pairs are disjoint.(so if we decide what to do with a particular pair \((a, b)\), we’re not affecting any other pair.)

For each pair \((a, b)\), we can choose:
- only \(a\), or
- only \(b\), or
- neither

But we cannot choose both \(a\) and \(b\), as their sum would be \(2n + 1\).

So,for each of the \(n\) pairs, we have 3 valid options which makes the total number of valid subsets as:  
\[
3^n
\]