IMC 2022 · Day 2 · P8

Hint:

We prove that $$\mathsf{E}(m) = \frac{2kn}{n + k - 1} - 2 \frac{k! \, n!}{(k + n - 1)!}.$$ Let $A_1, \dots, A_n$ be blue points. Fix $i \in \{1, \dots, n\}$. Enumerate our $n + k$ points starting from a blue point $A_i$ counterclockwise as $A_i, X_{1,i}, X_{2,i}, \dots, X_{(n+k-1),i}$. Denote the minimal index $j$ for which the point $X_{j,i}$ is blue as $m(i)$. So, $A_i X_{m(i),i}$ is a side of the convex hull of blue points. Denote by $b_i$ the following random variable: $$b_i = \begin{cases} 1, & \text{if the chord } A_i X_{m(i),i} \text{ contains a side of } F \\ 0, & \text{otherwise.} \end{cases}$$ Define analogously $k$ random variables $r_1, \dots, r_k$ for the red points. Clearly, $$\tag{$\heartsuit$} m = b_1 + \dots + b_n + r_1 + \dots + r_k.$$ We proceed with computing the expectation of each $b_i$ and $r_j$. Note that $b_i = 0$ if and only if all red points lie on the side of the line $A_i X_{m(i),i}$. This happens either if $m(i) = 1$, i.e., the point $X_{i,1}$ is blue (which happens with probability $\frac{n-1}{k+n-1}$), or if $i = k + 1$, points $X_{1,i}, \dots, X_{k,i}$ are red, and points $X_{k+1,i}, \dots, X_{k+n-1,i}$ are blue (which happens with probability $1 / \binom{k+n-1}{k}$, since all subsets of size $k$ of $\{1, 2, \dots, n+k-1\}$ have equal probabilities to correspond to the indices of red points between $X_{1,i}, \dots, X_{n+k-1,i}$). Thus the expectation of $b_i$ equals $1 - \frac{n-1}{k+n-1} - 1 / \binom{k+n-1}{k} = \frac{k}{n+k-1} - \frac{k! (n-1)!}{(k+n-1)!}$. Analogously, the expectation of $r_j$ equals $\frac{n}{n+k-1} - \frac{n! (k-1)!}{(k+n-1)!}$. It remains to use $(\heartsuit)$ and linearity of expectation.

Let $C_1, \dots, C_{n+k}$ be the colours of the points, scanned counterclockwise from a fixed point on the circle. We consider the sequence as cyclic (so $C_{n+k}$ is also adjacent to $C_1$). There are two cases: Either (i) all red points appear contiguously, followed by all blue points contiguously, or (ii) the red and blue points alternate at least twice. It can be seen that in the second case, $m$ is exactly equal to the number of colour changes in the $C_i$ sequence: For example, if $C_i$ is red and $C_{i+1}$ is blue, then the intersection of the red chord from $C_i$ to the next red point with the blue chord from $C_{i+1}$ to the previous blue point is a vertex of $F$, and every vertex is of this form. Case (i) is exceptional, as we have two colour changes, but $m = 0$, so it is 2 less than the number of changes in that case.

Now observe that the distribution of $C_i$ is purely combinatorial: Each of the $\binom{n+k}{n,k}$ distributions of colours is equally likely (for example, because we can generate the distribution by first choosing all $n + k$ points on the circle, and then assigning colours uniformly). In particular the probability that $C_i C_{i+1}$ is a colour change is exactly $\frac{2nk}{(n+k)(n+k-1)}$, and by lineraity of expectation, the total expected number of color changes (including $i = n+k$) is $n + k$ times this, i.e. $\frac{2nk}{n+k-1}$.

To get the expected value of $m$, we must subtract from the above 2 times the probability of case (i). Exactly $n + k$ of the $\binom{n+k}{n,k}$ distributions belong to case (i), so we must subtract $2 (n+k) \binom{n+k}{n,k}^{-1} = 2 \frac{n! k!}{(n+k-1)!}$, as claimed.

Let $A_1, \dots, A_n$ be the blue points and $B_1, \dots, B_k$ be the red points. For every pair of blue points $A_i$, $A_j$, $1 \leqslant i < j \leqslant n$, we evaluate the probability $p$ that $A_i A_j$ contains a side of $F$ (it obviously does not depend on the choice of $i$ and $j$). By $q$ denote the analogous probability for the red points. Then by linearity of expectation we have $\mathsf{E} m = \binom{n}{2} p + \binom{k}{2} q$.

We proceed with finding $p$. Without loss of generality $i = 1$, $j = 2$. Let the length of the circle be 1, and the length of arc $A_1 A_2$ (counterclockwise from $A_1$ to $A_2$) be $x$. Then $x$ is uniformly distributed on $[0, 1]$. Then $A_1 A_2$ contains a side of $F$ if

(i) all blue points are on the same side of $A_1 A_2$, but

(ii) the red points are not on the same side of $A_1 A_2$.

The probability of (i) is $x^{n-2} + (1-x)^{n-2}$. The probability of (ii) is $1 - (x^k + (1-x)^{n-k})$.

Thus, using Beta function value $B(a, b) = \int_0^1 x^{a-1} (1-x)^{b-1}\,dx = B(a, b)$

= \frac{(a-1)!(b-1)!}{(a+b-1)!} for positive integers $a, b$ $$\begin{align*} p &= \int_0^1 (x^{n-2} + (1-x)^{n-2}) (1 - (x^k + (1-x)^{n-k}))\,dx = \frac{2}{n-1} - \frac{2}{n+k-1} - 2 B(n-1, k+1) \\ &= \frac{2}{n-1} - \frac{2}{n+k-1} - 2 \frac{(n-2)! \, k!}{(n+k-1)!}. \end{align*}$$ Next, $$\binom{n}{2} p = n - \frac{n(n-1)}{n+k-1} - \frac{n! \, k!}{(n+k-1)!} = \frac{nk}{n+k-1} - \frac{n! \, k!}{(n+k-1)!},$$ and by symmetry $\binom{k}{2} q$ takes the same value (that is in agreement with the observation that red and blue sides of $F$ alternate).