Solution: 2019 Winter Final - 21

Author: Michiel Smid

Question

Let $n \geq 2$ be an integer. You are given $n$ beer bottles $B_1,B_2,...,B_n$ and two cider bottles $C_1$ and $C_2$. Consider a uniformly random permutation of these $n + 2$ bottles. The positions in this permutation are numbered $1,2,...,n + 2$. Consider the random variable

X = the position of the leftmost beer bottle.

What is the expected value $\mathbb{E}(X)$ of the random variable $X$?

(a)

$\frac{n}{n + 2} + \frac{2n + 2}{(n + 1)(n + 2)}$

(b)

$\frac{n}{n + 2} + \frac{4n + 6}{(n + 1)(n + 2)}$

(c)

$\frac{n}{n + 2} + \frac{2n + 6}{(n + 1)(n + 2)}$

(d)

$\frac{n}{n + 2} + \frac{4n + 2}{(n + 1)(n + 2)}$

Solution

So this question mainly focuses on the position of the leftmost beer bottle

Let S be the set of all possible permutations of the n+2 bottles

$|S| = (n+2)!$

We then have 3 real cases

Let A = The leftmost beer bottle is in the first position

The 2 cider bottles can be placed anywhere from positions 2 to n+2: $\binom{n+1}{2}$

There are 2 permutations for the cider bottles

There are n! permutations for the n beer bottles

$|A| = \binom{n+1}{2} \cdot 2 \cdot n!$
The leftmost beer bottle is in the second position

The first cider bottle is locked into position 1, and the second cider bottle can be placed anywhere from positions 3 to n+2: $\binom{n}{1}$

There are 2 permutations for the cider bottles

There are n! permutations for the n beer bottles

$|B| = \binom{n}{1} \cdot 2 \cdot n!$
The leftmost beer bottle is in the third position

The first cider bottle is locked into position 1, the second cider bottle is locked into position 2

there are 2 permutations for the cider bottles

There are n! permutations for the n beer bottles

$|C| = 2 \cdot n!$
Profit

$ \mathbb{E}(X) = 1 \cdot \Pr(A) + 2 \cdot \Pr(B) + 3 \cdot \Pr(C) $

$ \mathbb{E}(X) = 1 \cdot \frac{|A|}{|S|} + 2 \cdot \frac{|B|}{|S|} + 3 \cdot \frac{|C|}{|S|} $

$ \mathbb{E}(X) = 1 \cdot \frac{ \binom{n+1}{2} \cdot 2 \cdot n!}{(n+2)!} + 2 \cdot \frac{ \binom{n}{1} \cdot 2 \cdot n!}{(n+2)!} + 3 \cdot \frac{2 \cdot n!}{(n+2)!} $

$ \mathbb{E}(X) = \frac{2 \cdot \frac{(n+1)!}{2!(n-1)!}}{(n+2)(n+1)} + 2 \cdot \frac{n \cdot 2}{(n+2)(n+1)} + 3 \cdot \frac{2}{(n+2)(n+1)} $

$ \mathbb{E}(X) = \frac{(n+1)n}{(n+2)(n+1)} + \frac{4n}{(n+2)(n+1)} + \frac{6}{(n+2)(n+1)} $

$ \mathbb{E}(X) = \frac{n}{n+2} + \frac{4n+6}{(n+2)(n+1)} $