Solution: 2017 Fall Final - 24

Author: Michiel Smid

Question

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)}$

Solution

Let $X_i$ be 1 if the students at positions $i$ and $2i$ are politically correct

Let S be all possible combinations
We choose k positions for the politically correct students: $ \binom{n}{k} $
$ |S| = \binom{n}{k} $
Let $X_i=1$ be the event that the students at positions $i$ and $2i$ are politically correct
2 students at those positions are both politicall correct
We choose k-2 positions for the politically correct out of n-2 remaining positions: $ \binom{n-2}{k-2} $
$ |X_i=1| = \binom{n-2}{k-2} $
$ Pr (X_i=1 ) = \frac{X_i=1|}{|S|} $
$ Pr (X_i=1 ) = \frac{\binom{n-2}{k-2}}{\binom{n}{k}} $
$ Pr (X_i=1 ) = \frac{ \frac{ (n-2)! }{ (k-2)! (n-k)! }}{ \frac{n!}{k! (n-k)! }} $
$ Pr (X_i=1 ) = \frac{ (n-2)! }{ (k-2)! (n-k)! } \cdot \frac{k! (n-k)!}{n!} $
$ Pr (X_i=1 ) = \frac{ (n-2)! }{ (k-2)! (n-k)! } \cdot \frac{k! (n-k)!}{n \cdot (n-1) \cdot (n-2)!} $
$ Pr (X_i=1 ) = \frac{ 1 }{ (k-2)! (n-k)! } \cdot \frac{k! (n-k)!}{n \cdot (n-1) } $
$ Pr (X_i=1 ) = \frac{ 1 }{ (k-2)! } \cdot \frac{k!}{n \cdot (n-1) } $
$ Pr (X_i=1 ) = \frac{ 1 }{ (k-2)! } \cdot \frac{k \cdot (k-1) \cdot (k-2)! }{n \cdot (n-1) } $
$ Pr (X_i=1 ) = \frac{ 1 }{ 1 } \cdot \frac{k \cdot (k-1) \cdot 1 }{n \cdot (n-1) } $
$ Pr (X_i=1 ) = \frac{k \cdot (k-1) }{n \cdot (n-1) } $

Well, $S_n$ corresponds to $S_{ \frac{n}{2} }$

$S_{n-2}$ corresponds to $S_{ \frac{n}{2}-1}$

$S_{n-4}$ corresponds to $S_{ \frac{n}{2}-2}$

Half of everyone has a corresponding junior

$ E(X) = \sum_{i=1}^{n/2} Pr(X_i=1) $

$ E(X) = \sum_{i=1}^{n/2} \frac{k \cdot (k-1) }{n \cdot (n-1) } $

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