# Set Theory and Expected Value problem

For any subset $$S\subseteq\{1,2,\ldots,15\}$$, call a number $$n$$ an anchor for $$S$$ if $$n$$ and $$n+\#(S)$$ are both elements of $$S$$. For example, $$4$$ is an anchor of the set $$S=\{4,7,14\}$$, since $$4\in S$$ and $$4+\#(S) = 4+3 = 7\in S$$.

Given that $$S$$ is randomly chosen from all $$2^{15}$$ subsets of $$\{1,2,\ldots,15\}$$ (with each subset being equally likely), what is the expected value of the number of anchors of $$S$$?

I don't know how to start this problem.

"...I don't know how to start this problem."

For $$n\in\left\{ 1,2,\dots,15\right\}$$ let $$a_{n}$$ denotes the number of subsets of $$\left\{ 1,2,\dots,15\right\}$$ with the property that $$n$$ is an anchor of it.

Further let $$X_{n}$$ take value $$1$$ if $$n$$ is an anchor of the randomly chosen $$S$$ and let it take value $$0$$ otherwise.

Then $$X:=X_{1}+\cdots+X_{15}$$ is the number of anchors of $$S$$ and with linearity of expectation we find:

$$\mathbb{E}X=\sum_{n=1}^{15}\mathbb{E}X_{n}=\sum_{n=1}^{15}P\left(X_{n}=1\right)=\sum_{n=1}^{15}P\left(n\text{ is an anchor of }S\right)=2^{-15}\sum_{n=1}^{15}a_{n}$$

Now it remains to find the $$a_{n}$$.

Maybe you should first give that a try yourself.