HMMT 二月 2005 · 冲刺赛 · 第 36 题

英文解析

36. One hundred people are in line to see a movie. Each person wants to sit in the frontrow, which contains one hundred seats, and each has a favorite seat, chosen randomlyand independently. They enter the row one at a time from the far right. As they walk,
    if they reach their favorite seat, they sit, but to avoid stepping over people, if theyencounter a person already seated, they sit to that person’s right. If the seat furthestto the right is already taken, they sit in a different row. What is the most likely numberof people that will get to sit in the first row?
    Solution: 10
    Let S ( i ) be the favorite seat of the i th person, counting from the right. Let P ( n ) bethe probability that at least n people get to sit. At least n people sit if and only if
    S (1) ≥ n , S (2) ≥ n − 1, . . . , S ( n ) ≥ 1. This has probability:
    100 − ( n − 1) 100 − ( n − 2) 100 100!
    P ( n ) = · · · · = .
    100 100 100 (100 − n )! · 100 n
    The probability, Q ( n ), that exactly n people sit is
    100! 100! 100! · n
    P ( n ) − P ( n + 1) = − = .
    n n +1 n +1
    (100 − n )! · 100 (99 − n )! · 100 (100 − n )! · 100
    Now,
    n 2
    Q ( n ) 100! · n (101 − n )! · 100 n (101 − n ) 101 n − n = · = = ,
    n +1
    Q ( n − 1) (100 − n )! · 100 100! · ( n − 1) 100( n − 1) 100 n − 100
    which is greater than 1 exactly when n − n − 100 < 0, that is, for n ≤ 10. Therefore,2
    the maximum value of Q ( n ) occurs for n = 10.