Good Number?

Suppose $n$ is a good number with respect to a set $X$ with $k$ elements, and all the elements of $X$ are chosen randomly from the set $\{1, 2, ..., N\}$

Then $n, n+k\in X$ , and so we can subject 2 constraints to the values of $k$ : $k\ge 2$ and $k\le N-n$

The remaining $k-2$ elements of $X$ can be chosen from the remaining $N-2$ elements

Thus, there are $\binom{N-2}{k-2}$ such sets $X$ , and this gives us for each fixed $n$ , there are $\binom{N-2}{0}+\binom{N-2}{1}+...+\binom{N-2}{N-2-n}$

sets such that $n$ is a good number.

Notice that $n$ is at most $N-2$ (otherwise the constraints of $k$ will be violated) and at least $1$ .

Summing over all possible values of $n$ , we have the total number of good number is $S=(N-2)\binom{N-2}{0}+(N-3)\binom{N-2}{1}+...+\binom{N-2}{N-3}$

Applying the indentity $\binom{m}{r}=\binom{m}{m-r}$ , we have $S=(N-2)\binom{N-2}{N-2}+(N-3)\binom{N-2}{N-3}+...+\binom{N-2}{1}$

Adding these, we obtain $2S=(N-2)[\binom{N-2}{0}+\binom{N-2}{1}+...+\binom{N-2}{N-2}]=(N-2)2^{N-2}$

Hence, the expected value of the total number of good numbers is $\frac{S}{2^{N}}=\frac{(N-2)2^{N-3}}{2^N}=\frac{N-2}{8}$

For this particular problem, $N=2017$ , therefore the required expected value is $\frac{2017-2}{8}=\frac{2015}{8}=\boxed{251.875}$

Suppose that we are choosing subsets of $\{1,2,...,N\}$ randomly. Let $Z$ be the number of good numbers, and let $X_j$ be the random variable which is equal to $1$ if $j$ is a good number, and $0$ otherwise, for $1 \le j \le N$ . Then $Z = \sum_{j=1}^N X_j$ , so that $\mathbb{E}[Z] \;=\; \sum_{j=1}^N \mathbb{E}[X_j] \;=\; \sum_{j=1}^N p_j$ where $p_j$ is the probability that $j$ is a good number.

For any $1 \le j \le N$ and $0 \le k \le N$ , let $n_k(j)$ be the number of subsets of $\{1,2,3,...,N\}$ of size $k$ for which $j$ is good. Then $n_k(j) \; = \; \left\{ \begin{array}{lll} \binom{N-2}{k-2} & \hspace{1cm} & 1 \le j \le N-k \\ 0 & & \mathrm{o.w} \end{array}\right. \hspace{2cm} 0 \le k \le N$ (both $j$ and $j+k$ have to belong to $X$ , and we can choose the other $k-2$ elements freely). Thus $p_j \; = \; \frac{1}{2^N}\sum_{k=0}^N n_k(j) \; = \; \frac{1}{2^N} \sum_{k=2}^{N-j} \binom{N-2}{k-2} \; = \; \frac{1}{2^N}\sum_{k=0}^{N-2-j}\binom{N-2}{k} \hspace{2cm} 1 \le j \le N-2$ with $p_{N-1} = p_N = 0$ , and hence $\begin{aligned} \mathbb{E}[Z] & = \; \sum_{j=1}^N p_j \; = \; \frac{1}{2^N} \sum_{j=1}^{N-2}\sum_{k=0}^{N-2-j}\binom{N-2}{k} \; = \; \frac{1}{2^N} \Big[\sum_{j=0}^{N-2} \sum_{k=0}^{N-2-j}\binom{N-2}{k} - 2^{N-2}\Big] \\ & = \; \frac{1}{2^N}\Big[\sum_{{0 \le j,k \le N-2} \atop {j+k \le N-2}} \binom{N-2}{k} - 2^{N-2}\Big] \; = \; \frac{1}{2^N}\Big[\sum_{k=0}^{N-2}(N-1-k)\binom{N-2}{k} - 2^{N-2}\Big] \; = \; \frac{1}{2^N}\sum_{k=0}^{N-2}(N-2-k)\binom{N-2}{k} \\ & = \; \frac{1}{2^N}\sum_{k=0}^{N-3}(N-2-k)\binom{N-2}{k} \; = \; \frac{1}{2^N} \sum_{k=0}^{N-3} (N-2)\binom{N-3}{k} \; = \; \frac{1}{2^N} \times (N-2)2^{N-3} \\ & = \; \tfrac18(N-2) \end{aligned}$ With $N = 2017$ this makes the answer $\tfrac{2015}{8} = \boxed{251.875}$ .