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"

(→‎Solution)
(→‎Solution)
Line 7: Line 7:
 
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>.
 
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 this definition best:
+
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>
 
<cmath>A = (\underbrace{2,4,5,6}_{\text{Lefty terms}},10,\underbrace{9,8,7,3,1}_{\text{Righty terms}}).</cmath>
−
Assign every element 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. 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>.
+
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. An analogous argument proves that the righty terms are in decreasing order.
+
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 each of <math>4</math> and <math>9</math> is lefty or righty. By symmetry, the case where <math>4</math> and <math>9</math> are both lefty is equivalent to the case where <math>4</math> and <math>9</math> are both righty, and the case where <math>4</math> is left and <math>9</math> is righty is equivalent to the case where <math>4</math> is righty and <math>9</math> is lefty. Hence, we really only have two cases to consider.
  
  
  
−
If <math>a_{r-1}</math> is defined (that is, if <math>r > 1</math>), we have <math>a_{r} > a_{r-1}</math> because the largest term of <math>A</math> is <math>10</math>. Next, consider <math>a_{r-2}</math> if it is defined. Notice that by the definition of a peaked permutation, we cannot have <math>a_{r-1} < a_{r-2}</math>. Since we obviously cannot have <math>a_{r-2} = a_{r-1}</math>, it follows that <math>a_{r-1} > a_{r-2}</math>. By analogous reasoning, <math>a_{r-1} > a_{r-2}</math> implies <math>a_{r-2} > a_{r-3}</math> if <math>a_{r-3}</math> is defined, and so on, until we arrive at <math>a_2 > a_1</math>. Therefore, the sequence <math>a_1, a_2, \dots, a_r</math> is increasing. Analogously, we can show that the sequence <math>a_r, a_{r+1}, \dots, a_{10}</math> is decreasing.
 
  
−
It is straightforward to verify that every permutation <math>(b_1, b_2, \dots, b_{10})</math> of <math>(1,2,\dots, 10)</math> satisfying <math>b_1 < b_2 < \cdots b_s = 10</math> and <math>10 = b_s > b_{s+1} > \cdots > b_{10}</math> is in fact peaked. Thus, we have here a more convenient definition of a peaked permutation.
 
  
−
Let <math>N</math> be the number of indices <math>\ell</math> such that <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>. The key to finding this value is to think about how to construct <math>A</math>, utilizing our new characterization of peaked permutations. Begin with the term <math>10</math> of <math>A</math>. For each term <math>1\le d \le 9</math> of <math>A</math>, we choose whether <math>d</math> will lie to the left or to the right of <math>a_r=10</math> when <math>A</math> is written as <math>(a_1,a_2,\dots, a_{10})</math>. Then, arranging the terms left of <math>10</math> in increasing order and arranging the terms right of <math>10</math> in decreasing order yields a peaked permutation <math>A</math>. Importantly, this <math>A</math> is uniquely determined by how we assign each term <math>1\le d\le 9</math> either to the right or to the left of <math>10</math>.
+
For the sake of notation, let <math>P_d</math> denote the probability that the term <math>1\le d\le 10</math> lies between the terms <math>a_p = 4</math> and <math>a_p = 9</math>. In particular, linearity of expected value tells us that <math>\mathbb{E}[N] = P_1 + P_2 + \cdots + P_{10}</math>.
 +
 
 +
<i>Case 1:</i> <math>4</math> and <math>9</math> are both lefty
 +
 
 +
<i>Case 2:</i> <math>4</math> and <math>9</math> are both righty. By symmetry, this case is equivalent to the previous one, so the expected value
 +
 
 +
<i>Case 3:</i> <math>d=10</math>.
 +
 
 +
<i>Case 4:</i> <math>d=4,9</math>. Trivially, we have <math>P_4 = P_9 = 0</math>.
 +
 
 +
 
  
 
When <math>A</math> is written as <math>(a_1, a_2, \dots, a_{10})</math>, either <math>a_r = 10</math> lies between <math>a_p = 4</math> and <math>a_q = 9</math> or it does not. Each possibility is equally likely; whether <math>4</math> is assigned to left or to the right of <math>10</math>, there is a <math>\tfrac{1}{2}</math> chance that <math>9</math> is assigned to the same side of <math>10</math> as <math>4</math>. Thus, we will determine the expected value of <math>N</math> in each of these cases and then take their average to find <math>\mathbb{E}[N]</math>. We introduce some useful notation right before we do so; for each term <math>1\le d \le 10</math>, let <math>P_d</math> denote the probability that <math>d</math> lies between the terms <math>4</math> and <math>9</math> in <math>A</math>. In particular, note that <math>\mathbb{E}[N] = P_1 + P_2 + \cdots + P_{10}</math> by the linearity of expected value.
 
When <math>A</math> is written as <math>(a_1, a_2, \dots, a_{10})</math>, either <math>a_r = 10</math> lies between <math>a_p = 4</math> and <math>a_q = 9</math> or it does not. Each possibility is equally likely; whether <math>4</math> is assigned to left or to the right of <math>10</math>, there is a <math>\tfrac{1}{2}</math> chance that <math>9</math> is assigned to the same side of <math>10</math> as <math>4</math>. Thus, we will determine the expected value of <math>N</math> in each of these cases and then take their average to find <math>\mathbb{E}[N]</math>. We introduce some useful notation right before we do so; for each term <math>1\le d \le 10</math>, let <math>P_d</math> denote the probability that <math>d</math> lies between the terms <math>4</math> and <math>9</math> in <math>A</math>. In particular, note that <math>\mathbb{E}[N] = P_1 + P_2 + \cdots + P_{10}</math> by the linearity of expected value.

Revision as of 13:29, 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 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$.

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