0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

"...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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.