Question: 2017 Fall Final - 24

Author: Michiel Smid

Let $n$ and $k$ be integers such that $n$ is even, $n \geq 2$, and $1 \leq k \leq n$.
The Carleton Computer Science Society (CCSS) is having their annual ~~Christmas~~ Holiday Season Party, which is attended by $n$ students.

(a)	$k$ of these $n$ students are politically correct and, thus, refuse to say Merry Christmas. Instead, they say Happy Holidays.
(b)	$n - k$ of these $n$ students do not care about political correctness and, thus, they say Merry Christmas.

Consider a uniformly random permutation of these $n$ students. The positions in this permutation are numbered as $1,2,...,n$.
Define the following random variable $X$:

X = the number of positions $i$ with $1 \leq i \leq \left. n \middle/ 2 \right.$ such that both students at positions $i$ and $2i$ are politically correct.

What is the expected value $\mathbb{E}(X)$ of the random variable $X$?
Hint: Use indicator random variables.

(a)

$n \cdot \frac{(k - 1)(k - 2)}{n(n - 1)}$

(b)

$\frac{n}{2} \cdot \frac{k(k - 1)}{n(n - 1)}$

(c)

$\frac{n}{2} \cdot \frac{(k - 1)(k - 2)}{n(n - 1)}$

(d)

$n \cdot \frac{k(k - 1)}{n(n - 1)}$