HMMT-Nov 2016 guts, Problem 28

The numbers 1-10 are written in a circle randomly. Find the expected number of numbers which are at least 2 larger than an adjacent number.

Solution: For $1 \leq i \leq 10$, let $X_{i}$ be the random variable that is 1 if the $i$ in the circle is at least 2 larger than one of its neighbors, and 0 otherwise. The random variable representing number of numbers that are at least 2 larger than one of their neighbors is then just $X_{1}+X_{2}+\cdots+X_{10}$. The expected value $\mathbb{E}\left[X_{1}+X_{2}+\cdots+X_{10}\right]$ is equal to $\mathbb{E}\left[X_{1}\right]+\mathbb{E}\left[X_{2}\right]+\cdots+\mathbb{E}\left[X_{10}\right]$ by the linearity of expectation, so it suffices to compute $\mathbb{E}\left[X_{i}\right]$ for all $1 \leq i \leq 10$. By the definition of expected value, $\mathbb{E}\left[X_{i}\right]=1 \cdot P$ (the $i$ is at least 2 larger than one of its neighbors $)+0$. $P($ it is not at least 2 larger than either of its neighbors $)=P($ the $i$ is at least 2 larger than one of its neighbors $)=$ $1-P$ (the $i$ is at most 1 larger than both of its neighbors). For the last probability, $i$ 's neighbors must be drawn from the set $\{\max (1, i-1), \max (1, i-1)+1, \ldots, 10\}$, excluding $i$ itself. This set has $10-\max (1, i-1)$ elements, so there are a total of $(\underset{2}{10-\max (1, i-1)})$ sets of two neighbors for $i$ that satisfy the condition, out of a total of $\left(\begin{array}{c}9 \\ 2\end{array}\right)$ possible sets of two neighbors from all of the numbers that are not $i$. The last probability is then $\frac{\left(\begin{array}{c}10-\max (1, i-1) \\ 2\end{array}\right)}{\left(\begin{array}{l}9 \\ 2\end{array}\right)}$, so $\mathbb{E}\left[X_{i}\right]=1-\frac{\left(\begin{array}{c}10-\max (1, i-1) \\ 2\end{array}\right)}{\left(\begin{array}{l}9 \\ 2\end{array}\right)}$. The final sum we wish to calculate then becomes $\left.\left(1-\frac{\left(\begin{array}{l}9 \\ 2\end{array}\right)}{\left(\begin{array}{l}9 \\ 2\end{array}\right)}\right)+\left(1-\frac{\left(\begin{array}{l}9 \\ 2\end{array}\right)}{\left(\begin{array}{l}9 \\ 2\end{array}\right)}\right)+\left(1-\frac{\left(\begin{array}{l}8 \\ 2\end{array}\right)}{\left(\begin{array}{l}9 \\ 2\end{array}\right)}\right)+\left(1-\frac{\left(\begin{array}{l}7 \\ 2\end{array}\right)}{\left(\begin{array}{l}9 \\ 2\end{array}\right)}\right)+\cdots+\left(1-\frac{\left(\begin{array}{l}1 \\ 2\end{array}\right)}{(29}\right)\right)=$ $0+0+\left(1-\frac{28}{36}\right)+\left(1-\frac{21}{36}\right)+\cdots+(1-0)=\frac{17}{3}$. $\fbox{\frac{17}{3}}$.

Answer: \frac{17}{3}