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 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 parti- tioned correctly.

解析

A permutation of { 1 , 2 , . . . , 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 parti- tioned correctly. Proposed by: Mehtaab Sawhney 151 Answer: 105 Let σ be a permutation on { 1 , . . . , n } . Call m ∈ { 1 , . . . , n } a breakpoint of σ if { σ (1) , . . . , σ ( m ) } = { 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 k as our contiguous blocks. Now we just want to find E [ k ] = E [ X + · · · + X ] , 1 n where X = 1 if i is a breakpoint, and X = 0 otherwise. We use linearity of expectation and notice i i that i !( n − i )! E [ X ] = , i n ! since 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 ! i i =1 i =1 151 We can compute for n = 7 that the answer is . 105