Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2025 SSMO Accuracy Round Problems/Problem 8"

(→‎Problem)
(→‎Solution)
 
(2 intermediate revisions by the same user not shown)
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
 +
 +
Let <math>A = (a_1, a_2, \dots, a_{10})</math> be an arbitrary permutation in <math>\mathcal{S}</math>, let <math>p</math> and <math>q</math> be as in the problem statement, and let <math>1\le r \le 10</math> be the integer such that <math>a_r = 10</math>.
 +
 +
The key to solving this problem is to formulate a way of uniquely constructing every possible <math>A</math>. To do this, we first introduce two bits of intuitive terminology; we say that a term <math>a_x \ne a_r</math> of <math>A</math> is <i>lefty</i> if <math>x<r</math> and <i>righty</i> if <math>x>r</math>. An example showcases these definitions best:
 +
<cmath>A = (\underbrace{2,4,5,6}_{\text{Lefty terms}},10,\underbrace{9,8,7,3,1}_{\text{Righty terms}}).</cmath>
 +
Assign every term of <math>A</math> not equal to <math>10</math> to be either lefty or righty. We claim that this uniquely determines a peaked permutation <math>A</math>; 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 <math>A</math> is indeed peaked). For the sake of contradiction, suppose that there exist two lefty terms <math>a_{x_1} > a_{x_2}</math> with <math>x_1 < x_2</math>. However, we then have <math>a_{x_1} > a_{x_2}</math> and <math>a_{x_2} < a_r</math> with <math>1 \le x_1 < x_2 < r \le 10</math>; contradiction. Therefore, the lefty terms are in increasing order. A similar argument proves that the righty terms are in decreasing order.
 +
 +
Let <math>N</math> be the number of indices <math>\ell</math> such that <math>a_\ell</math> lies between <math>a_p = 4</math> and <math>a_q = 9</math> in <math>A</math>; that is, when either <math>p < \ell < q</math> or <math>p > \ell > q</math>. Note that <math>\mathbb{E}[|p-q|] = \mathbb{E}[N] + 1</math>, so we focus on finding <math>\mathbb{E}[N]</math>. We do this via casework on whether <math>4</math> and <math>9</math> lie on the same side of <math>10</math> in <math>A</math> or not.
 +
 +
<i>Case 1:</i> <math>4</math> and <math>9</math> lie on the same side of <math>10</math> (that is, they are both lefty or both righty). Clearly, <math>10</math> does not lie between <math>4</math> and <math>9</math>. Some term <math>d\ne 10</math> can only lie between <math>4</math> and <math>9</math> whenever <math>4 < d < 9</math>; there are <math>4</math> such <math>d</math>. Furthermore, <math>d</math> must lie on the same of <math>10</math> as <math>4</math> and <math>9</math>, which happens with probability <math>\tfrac{1}{2}</math>. By the linearity of expected value, the expected value of <math>N</math> in this case is <math> 4\cdot \tfrac{1}{2}  = 2</math>.
 +
 +
<i>Case 2:</i> <math>4</math> and <math>9</math> lie on opposite sides of <math>10</math> (that is, one of them is lefty and the other is righty). Clearly, <math>10</math> lies between <math>4</math> and <math>9</math>. Some term <math>d\ne 10</math> lies between <math>4</math> and <math>9</math> only when <math>4 < d < 10</math> (it is impossible that <math>9 < d < 10</math>); there are <math>4</math> such <math>d</math>. Then, <math>d</math> must lie on on the same side of <math>10</math> as <math>4</math>, which happens with probability <math>\tfrac{1}{2}</math>. The expected value of <math>N</math> in this case is thus <math>1 + 4\cdot \tfrac{1}{2} = 3</math>.
 +
 +
Each of the two cases just outlined occurs with probability <math>\tfrac{1}{2}</math>, so <math>\mathbb{E}[N] = \tfrac{1}{2}\cdot 2 + \tfrac{1}{2}\cdot 3 = \tfrac{5}{2}</math>. The expected value of <math>|p-q|</math> is <math>\tfrac{5}{2}+1 = \tfrac{7}{2}</math>, so the answer is <math>7+2 = \boxed{9}</math>.
 +
 +
~Sedro

Latest revision as of 14:02, 18 September 2025

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2025_SSMO_Accuracy_Round_Problems/Problem_8&oldid=260852"