8. For any subset $S \subseteq\{1,2, \ldots, 15\}$, a number $n$ is called an "anchor" for $S$ if $n$ and $n+|S|$ are both members of $S$, where $|S|$ denotes the number of members of $S$. Find the average number of anchors over all possible subsets $S \subseteq\{1,2, \ldots, 15\}$.
Solution:
$$
13 / 8
$$

We first find the sum of the numbers of anchors of all subsets $S$; this is equivalent to finding, for each $n$, the number of sets for which $n$ is an anchor, and then summing over all $n$. Suppose that $n$ is an anchor for $S$, and $S$ has $k$ elements. Then $n, n+k \in$ $S \Rightarrow k \geq 2$, and also $n+k \leq 15$, or $k \leq 15-n$. The remaining $k-2$ elements of $S$ (other than $n$ and $n+k$ ) may be freely chosen from the remaining 13 members of $\{1,2, \ldots, 15\}$, so we get $\binom{13}{k-2}$ possible sets $S$. Summing over all allowed values of $k$, we then have $\binom{13}{0}+\binom{13}{1}+\binom{13}{2}+\cdots+\binom{13}{13-n}$ sets with $n$ as an anchor. If we sum over all $n=1,2, \ldots, 13$ (since there are no possible values of $k$ when $n>13$ ), we get a total of
$$
13\binom{13}{0}+12\binom{13}{1}+11\binom{13}{2}+\cdots+\binom{13}{12} .
$$

If we call this quantity $A$, then, by symmetry, $2 A$ equals
$$
\begin{aligned}
13\binom{13}{0} & +12\left(\begin{array}{c}
13 \\
1 \\
13
\end{array}+11\binom{13}{2}+\cdots+2\binom{13}{2}+\cdots+12\left(\begin{array}{c}
13 \\
12 \\
12 \\
12
\end{array}\right)+13\binom{13}{13}\right. \\
& +\left(\binom{13}{0}+\binom{13}{1}+2+\binom{13}{13}\right]=13 \cdot 2^{13} .
\end{aligned}
$$

So $A=13 \cdot 2^{12}$ is the total number of anchors over all possible sets $S$. Finally, to find the average number of anchors, we divide by the number of sets, which is $2^{15}$; thus, the answer is $13 \cdot 2^{12} / 2^{15}=13 / 8$.