2025 SSMO Accuracy Round Problems/Problem 8

Problem

We say that a permutation $(a_1, a_2, \dots ,a_{10})$ of the integers $1$ through $10$ inclusive is peaked if there do not exist three integers $1\le i < j < k \le 10$ such that $a_i > a_j$ and $a_j< a_k$ . Let $\mathcal{S}$ be the set of all peaked permutations. If $a_p = 9$ and $a_q = 4$ , the expected value of $|p-q|$ over all permutations in $\mathcal{S}$ can be written as $\tfrac{m}{n}$ , where $m$ and $n$ are relatively prime positive integers. What is the value of $m+n$ ?

Solution

Let $A = (a_1, a_2, \dots, a_{10})$ be an arbitrary permutation in $\mathcal{S}$ , let $p$ and $q$ be as in the problem statement, and let $1\le r \le 10$ be the integer such that $a_r = 10$ .

The key to solving this problem is to formulate a way of uniquely constructing every possible $A$ . To do this, we first introduce two bits of intuitive terminology; we say that a term $a_x \ne a_r$ of $A$ is lefty if $x<r$ and righty if $x>r$ . An example showcases these definitions best: $A = (\underbrace{2,4,5,6}_{\text{Lefty terms}},10,\underbrace{9,8,7,3,1}_{\text{Righty terms}}).$ Assign every term of $A$ not equal to $10$ to be either lefty or righty. We claim that this uniquely determines a peaked permutation $A$ ; in fact, we show that the lefty terms must be in increasing order and the righty terms must be in decreasing order (and if this is the case, it is easy to verify that $A$ is indeed peaked). For the sake of contradiction, suppose that there exist two lefty terms $a_{x_1} > a_{x_2}$ with $x_1 < x_2$ . However, we then have $a_{x_1} > a_{x_2}$ and $a_{x_2} < a_r$ with $1 \le x_1 < x_2 < r \le 10$ ; contradiction. Therefore, the lefty terms are in increasing order. A similar argument proves that the righty terms are in decreasing order.

Let $N$ be the number of indices $\ell$ such that $a_\ell$ lies between $a_p = 4$ and $a_q = 9$ in $A$ ; that is, when either $p < \ell < q$ or $p > \ell > q$ . Note that $\mathbb{E}[|p-q|] = \mathbb{E}[N] + 1$ , so we focus on finding $\mathbb{E}[N]$ . We do this via casework on whether each of $4$ and $9$ is lefty or righty. By symmetry, the case where $4$ and $9$ are both lefty is equivalent to the case where $4$ and $9$ are both righty, and the case where $4$ is left and $9$ is righty is equivalent to the case where $4$ is righty and $9$ is lefty. Hence, we really only have two cases to consider.

For the sake of notation, let $P_d$ denote the probability that the term $1\le d\le 10$ lies between the terms $a_p = 4$ and $a_p = 9$ . In particular, linearity of expected value tells us that $\mathbb{E}[N] = P_1 + P_2 + \cdots + P_{10}$ .

Case 1: $4$ and $9$ are both lefty

Case 2: $4$ and $9$ are both righty. By symmetry, this case is equivalent to the previous one, so the expected value

Case 3: $d=10$ .

Case 4: $d=4,9$ . Trivially, we have $P_4 = P_9 = 0$ .

When $A$ is written as $(a_1, a_2, \dots, a_{10})$ , either $a_r = 10$ lies between $a_p = 4$ and $a_q = 9$ or it does not. Each possibility is equally likely; whether $4$ is assigned to left or to the right of $10$ , there is a $\tfrac{1}{2}$ chance that $9$ is assigned to the same side of $10$ as $4$ . Thus, we will determine the expected value of $N$ in each of these cases and then take their average to find $\mathbb{E}[N]$ . We introduce some useful notation right before we do so; for each term $1\le d \le 10$ , let $P_d$ denote the probability that $d$ lies between the terms $4$ and $9$ in $A$ . In particular, note that $\mathbb{E}[N] = P_1 + P_2 + \cdots + P_{10}$ by the linearity of expected value.

Case 1: $4$ and $9$ lie on opposite sides of $10$ . If this is the case, note that:

For terms $1\le d < 4$ , we have $P_d = 0$ because $d$ cannot lie between $4$ and $10$ or between $9$ and $10$ ; otherwise, the sequence of consecutive terms from $4$ to $10$ or from $9$ to $10$ would not be strictly monotonic.
For terms $4< d < 9$ , we have $P_d = \tfrac{1}{2}$ because $d$ lies between $4$ and $10$ when , but $d$ cannot lie between $9$ and $10$ for the reason outlined in the previous bullet. The probability that $d$ lies on the same side of $10$ as $4$ is $\tfrac{1}{2}$ .
Trivially, $P_4 = P_9 = 0$ and $P_{10} = 1$ .

Therefore, the expected value of $N$ in this case is $4(\tfrac{1}{2})+1 = 3$ .

Case 2: $4$ and $9$ lie on the same side of $10$ .

Page

Toolbox

Search

2025 SSMO Accuracy Round Problems/Problem 8

Problem

Solution