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)
 
(One intermediate revision by the same user not shown)
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. A similar argument proves that the righty terms are in decreasing order.
−
Therefore, the lefty terms are in increasing order. An analogous 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>.
  
−
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.
+
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>.
  
−
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.
+
~Sedro
−
 
 
−
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>.
 
−
 
 
−
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.
 
−
 
 
−
<i>Case 1:</i> <math>4</math> and <math>9</math> lie on opposite sides of <math>10</math>. If this is the case, note that:
 
−
<UL>
 
−
<LI>For terms <math>1\le d < 4</math>, we have <math>P_d = 0</math> because <math>d</math> cannot lie between <math>4</math> and <math>10</math> or between <math>9</math> and <math>10</math>; otherwise, the sequence of consecutive terms from <math>4</math> to <math>10</math> or from <math>9</math> to <math>10</math> would not be strictly monotonic.</LI>
 
−
<LI>For terms <math>4< d < 9</math>, we have <math>P_d = \tfrac{1}{2}</math> because <math>d</math> lies between <math>4</math> and <math>10</math> when , but <math>d</math> cannot lie between <math>9</math> and <math>10</math> for the reason outlined in the previous bullet. The probability that <math>d</math> lies on the same side of <math>10</math> as <math>4</math> is <math>\tfrac{1}{2}</math>.</LI>
 
−
<LI>Trivially, <math>P_4 = P_9 = 0</math> and <math>P_{10} = 1</math>.</LI>
 
−
</UL>
 
−
Therefore, the expected value of <math>N</math> in this case is <math>4(\tfrac{1}{2})+1 = 3</math>.
 
−
 
 
−
<i>Case 2:</i> <math>4</math> and <math>9</math> lie on the same side of <math>10</math>.
 

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"