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 $4$ and $9$ lie on the same side of $10$ in $A$ or not.

Case 1: $4$ and $9$ lie on the same side of $10$ (that is, they are both lefty or both righty). Clearly, $10$ does not lie between $4$ and $9$ . Some term $d\ne 10$ can only lie between $4$ and $9$ whenever $4 < d < 9$ ; there are $4$ such $d$ . Furthermore, $d$ must lie on the same of $10$ as $4$ and $9$ , which happens with probability $\tfrac{1}{2}$ . By the linearity of expected value, the expected value of $N$ in this case is $4\cdot \tfrac{1}{2} = 2$ .

Case 2: $4$ and $9$ lie on opposite sides of $10$ (that is, one of them is lefty and the other is righty). Clearly, $10$ lies between $4$ and $9$ . Some term $d\ne 10$ lies between $4$ and $9$ only when $4 < d < 10$ (it is impossible that $9 < d < 10$ ); there are $4$ such $d$ . Then, $d$ must lie on on the same side of $10$ as $4$ , which happens with probability $\tfrac{1}{2}$ . The expected value of $N$ in this case is thus $1 + 4\cdot \tfrac{1}{2} = 3$ .

Each of the two cases just outlined occurs with probability $\tfrac{1}{2}$ , so $\mathbb{E}[N] = \tfrac{1}{2}\cdot 2 + \tfrac{1}{2}\cdot 3 = \tfrac{5}{2}$ . The expected value of $|p-q|$ is $\tfrac{5}{2}+1 = \tfrac{7}{2}$ , so the answer is $7+2 = \boxed{9}$ .

~Sedro

Page

Toolbox

Search

2025 SSMO Accuracy Round Problems/Problem 8

Problem

Solution