HMMT 二月 2018 · COMB 赛 · 第 8 题
HMMT February 2018 — COMB Round — Problem 8
题目详情
英文原题
- A permutation of { 1 , 2 , . . . , 7 } is chosen uniformly at random. A partition of the permutation intocontiguous blocks is correct if, when each block is sorted independently, the entire permutation becomessorted. 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.
解析
英文解析
- A permutation of { 1 , 2 , . . . , 7 } is chosen uniformly at random. A partition of the permutation intocontiguous blocks is correct if, when each block is sorted independently, the entire permutation becomessorted. 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.
Proposed by: Mehtaab Sawhney
Answer:151
Let σ be a permutation on { 1 , . . . , n } . Call m ∈ { 1 , . . . , n } a breakpoint of σ if { σ (1) , . . . , σ ( m ) } =105
{ 1 , . . . , m } . Notice that the maximum partition is into k blocks, where k is the number of breakpoints:
if our breakpoints are m , . . . , m , then we take { 1 , . . . , m } , { m + 1 , . . . , m } , . . . , { m + 1 , . . . , m }
1 k 1 1 2 k − 1 kas our contiguous blocks.
Now we just want to find
E [ k ] = E [ X + · · · + X ] ,
1 nwhere X = 1 if i is a breakpoint, and X = 0 otherwise. We use linearity of expectation and noticei ithati !( n − i )!
E [ X ] = ,
n !isince this is the probability that the first i numbers are just 1 , . . . , i in some order. Thus,
( )
n n − 1
∑ ∑
i !( n − i )! n
E [ k ] = = .
n ! ii =1 i =1
We can compute for n = 7 that the answer is .151
105