HMMT-Feb 2022 comb, Problem 6

The numbers $1,2, \ldots, 10$ are randomly arranged in a circle. Let $p$ be the probability that for every positive integer $k<10$, there exists an integer $k^{\prime}>k$ such that there is at most one number between $k$ and $k^{\prime}$ in the circle. If $p$ can be expressed as $\frac{a}{b}$ for relatively prime positive integers $a$ and $b$, compute $100 a+b$.

Solution: Solution: Let $n=10$ and call two numbers close if there is at most one number between them and an circular permutation focused if only $n$ is greater than all numbers close to it. Let $A_{n}$ be the number of focused circular permutations of $\{1,2, \ldots, n\}$. If $n \geq 5$, then there are 2 cases: $n-1$ is either one or two positions from $n$. If $n-1$ is one position from $n$, it is either on its left or right. In this case, one can check a permutation is focused if and only if removing $n$ yields a focused permutation, so there are $2 A_{n-1}$ permutations in this case. If $n-1$ is two positions from $n$, there are $n-2$ choices for $k$, the element that lies between $n$ and $n-1$. One\\ can show that this permutation is focused if and only if removing both $n$ and $k$ and relabeling the numbers yields a focused permutation, so there are $2(n-2) A_{n-2}$ permutations in this case. Thus, we have $A_{n}=2 A_{n-1}+2(n-2) A_{n-2}$. If we let $p_{n}=A_{n} /(n-1)$ ! the probability that a random circular permutation is focused, then this becomes \[ p_{n}=\frac{2 p_{n-1}+2 p_{n-2}}{n-1} \] Since $p_{3}=p_{4}=1$, we may now use this recursion to calculate \[ p_{5}=1, p_{6}=\frac{4}{5}, p_{7}=\frac{3}{5}, p_{8}=\frac{2}{5}, p_{9}=\frac{1}{4}, p_{10}=\frac{13}{90} \] $\fbox{1390}$.

Answer: 1390