IMO Hk TST

a.
The answer is $2^{2n-1} - \frac{1}{2}\binom{2n}{n}$.

A subset $T$ of $S$ is called a bad subset if in $T$ the number of odd elements is greater than the number of even elements. A subset of $S$ is neither good nor bad if it has exactly $k$ odd elements and $k$ even elements for some $k = 0, 1, \dots, n$. Since there are $n$ odd elements and $n$ even elements in $S$, the number of subsets which are neither good nor bad is
$$\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$$
by Vandermonde's identity.

Now, by symmetry, the number of good subsets is the same as the number of bad subsets. As there are $2^{2n}$ subsets of $S$ in total, the total number of good subsets is
$$\frac{1}{2}\left[2^{2n} - \binom{2n}{n}\right] = 2^{2n-1} - \frac{1}{2}\binom{2n}{n}.$$

b.
The answer is $2^{2n-2}(2n^2 + n) - n^2\binom{2n-1}{n}$.

We first count the number $N_1$ of good subsets containing a particular even number. Suppose such a good subset contains $i$ more even numbers and $j$ odd numbers. Then we need $i \ge j$. As there are $n-1$ even numbers remaining and $n$ odd numbers in total, we have
$$N_1 = \sum_{i=0}^{n-1} \sum_{j=0}^{i} \binom{n-1}{i} \binom{n}{j} = \sum_{i=0}^{n-1} \sum_{k=n-i}^{n} \binom{n-1}{i} \binom{n}{k} = \sum_{i+k \ge n} \binom{n-1}{i} \binom{n}{k}$$
by using the change of variable $k = n-j$. Note that this is equal to the sum of coefficients of all $x^m$ with $m \ge n$ in $(1+x)^{n-1}(1+x)^n = (1+x)^{2n-1}$. Thus, we obtain
$$N_1 = \sum_{m=n}^{2n-1} \binom{2n-1}{m} = \frac{1}{2} \sum_{m=0}^{2n-1} \binom{2n-1}{m} = 2^{2n-2}.$$

Similarly, we count the number $N_2$ of good subsets containing a particular odd number. Suppose such a good subset contains $i \ge 2$ even numbers and $j$ more odd numbers. Then we need $i \ge j + 2$. This implies
$$\begin{align*} N_2 &= \sum_{i=2}^{n} \sum_{j=0}^{i-2} \binom{n}{i} \binom{n-1}{j} \\ &= \sum_{i=2}^{n} \sum_{k=n+1-i}^{n-1} \binom{n}{i} \binom{n-1}{k} \\ &= \sum_{i+k \ge n+1} \binom{n}{i} \binom{n-1}{k} \\ &= \sum_{m=n+1}^{2n-1} \binom{2n-1}{m} \\ &= \frac{1}{2} \left( \sum_{m=0}^{2n-1} \binom{2n-1}{m} - \binom{2n-1}{n-1} - \binom{2n-1}{n} \right) \\ &= 2^{2n-2} - \binom{2n-1}{n}. \end{align*}$$

Now, the sum of all the elements in all the good subsets of $S$ is
$$\begin{align*} N_1(2+4+\cdots+2n) + N_2(1+3+\cdots+(2n-1)) \\ &= 2^{2n-2} \cdot n(n+1) + \left[ 2^{2n-2} - \binom{2n-1}{n} \right] \cdot n^2 \\ &= 2^{2n-2}(2n^2+n) - n^2 \binom{2n-1}{n}. \end{align*}$$