, 2014

Solution:
Let us solve a more generalized version of the problem: Let $S$ be a set with $2n+1$ elements, and partition $S$ into sets $A_{0}, A_{1}, \ldots, A_{n}$ such that $|A_{0}| = 1$ and $|A_{1}| = |A_{2}| = \cdots = |A_{n}| = 2$. (In this problem, we have $A_{0} = \{0\}$ and $A_{k} = \{k, -k\}$ for $k = 1, 2, \ldots, 100$.) Let $T$ be a randomly chosen $m$-element subset of $S$. What is the expected number of $A_{k}$'s that have a representative in $T$?

For $k = 0, 1, \ldots, n$, let $w_{k} = 1$ if $T \cap A_{k} \neq \emptyset$ and $0$ otherwise, so that the number of $A_{k}$'s that have a representative in $T$ is equal to $\sum_{k=0}^{n} w_{k}$. It follows that the expected number of $A_{k}$'s that have a representative in $T$ is equal to

$$\mathrm{E}\left[w_{0} + w_{1} + \cdots + w_{n}\right] = \mathrm{E}\left[w_{0}\right] + \mathrm{E}\left[w_{1}\right] + \cdots + \mathrm{E}\left[w_{n}\right] = \mathrm{E}\left[w_{0}\right] + n\, \mathrm{E}\left[w_{1}\right]$$

since $\mathrm{E}\left[w_{1}\right] = \mathrm{E}\left[w_{2}\right] = \cdots = \mathrm{E}\left[w_{n}\right]$ by symmetry.

Now $\mathrm{E}\left[w_{0}\right]$ is equal to the probability that $T \cap A_{0} \neq \emptyset$, that is, the probability that the single element of $A_{0}$ is in $T$, which is $m/(2n+1)$. Similarly, $\mathrm{E}\left[w_{1}\right]$ is the probability that $T \cap A_{1} \neq \emptyset$, that is, the probability that at least one of the two elements of $A_{1}$ is in $T$. Since there are $\binom{2n-1}{m}$ $m$-element subsets of $S$ that exclude both elements of $A_{1}$, and there are $\binom{2n+1}{m}$ $m$-element subsets of $S$ in total, we have that

$$\mathrm{E}\left[w_{1}\right] = 1 - \frac{\binom{2n-1}{m}}{\binom{2n+1}{m}} = 1 - \frac{(2n-m)(2n-m+1)}{2n(2n+1)}$$

Putting this together, we find that the expected number of $A_{k}$'s that have a representative in $T$ is
$$\frac{m}{2n+1} + n - \frac{(2n-m+1)(2n-m)}{2(2n+1)}$$

In this particular problem, we have $n = 100$ and $m = 50$, so substituting these values gives our answer of $\frac{8825}{201}$.