Practice By Tag: COMP 2804: Discrete Structures II

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