返回题库

HMMT 二月 2018 · COMB 赛 · 第 8 题

HMMT February 2018 — COMB Round — Problem 8

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. 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.
解析

英文解析

  1. 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