Library / /1287 of 1394

, 2018

Combinatorics Difficulty 6.0 AIME, harder Prove it United States

Problem:
A permutation of $\{1,2, \ldots, 7\}$ is chosen uniformly at random. A partition of the permutation into contiguous blocks is correct if, when each block is sorted independently, the entire permutation becomes sorted. For example, the permutation $(3,4,2,1,6,5,7)$ can be partitioned correctly into the blocks $[3,4,2,1]$ and $[6,5,7]$ , since when these blocks are sorted, the permutation becomes $(1,2,3,4,5,6,7)$ .
Find the expected value of the maximum number of blocks into which the permutation can be partitioned correctly.

Solution

Solution:
Let $\sigma$ be a permutation on $\{1, \ldots, n\}$ . Call $m \in\{1, \ldots, n\}$ a breakpoint of $\sigma$ if $\{\sigma(1), \ldots, \sigma(m)\}=\{1, \ldots, m\}$ . Notice that the maximum partition is into $k$ blocks, where $k$ is the number of breakpoints: if our breakpoints are $m_{1}, \ldots, m_{k}$ , then we take $\{1, \ldots, m_{1}\},\{m_{1}+1, \ldots, m_{2}\}, \ldots,\{m_{k-1}+1, \ldots, m_{k}\}$ as our contiguous blocks.

Now we just want to find
$\mathbb{E}[k]=\mathbb{E}\left[X_{1}+\cdots+X_{n}\right]$
where $X_{i}=1$ if $i$ is a breakpoint, and $X_{i}=0$ otherwise. We use linearity of expectation and notice that
$\mathbb{E}\left[X_{i}\right]=\frac{i!(n-i)!}{n!}$
since this is the probability that the first $i$ numbers are just $1, \ldots, i$ in some order. Thus,
$\mathbb{E}[k]=\sum_{i=1}^{n} \frac{i!(n-i)!}{n!}=\sum_{i=1}^{n}\binom{n}{i}^{-1}$
We can compute for $n=7$ that the answer is $\frac{151}{105}$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.