HMMT 二月 2011 · 冲刺赛 · 第 33 题

英文解析

33. [ 25 ] Find the number of sequences consisting of 100 R ’s and 2011 S ’s that satisfy the property thatamong the first k letters, the number of S ’s is strictly more than 20 times the number of R ’s for all
    1 ≤ k ≤ 2111.
    ( )
    2111
    Answer:11
    2111 100
    Given positive integers r and s such that s ≥ 20 r , let N ( s, r ) denote the number of sequences of scopies of S and r copies of R such that for all 1 ≤ k ≤ r + s − 1, among the first k letters, the numberof S ’s is strictly more than 20 times the number of R ’s. We claim that
    ( )
    s − 20 r s + r
    N ( s, r ) = .
    s + r s
    We induct on s + r . For the base case, note that N (20 r, r ) = 0 for all r and N ( s, 0) = 1 for all s .
    Assume the formula holds up to r + s − 1. We now construct a path in the Cartesian plane as follows:
    Let R represent moving one unit to the left and S represent moving one unit up. This induces abijection between sequences of S ’s and R s and lattice paths from the origin to the point ( r, s ) thatare above the line y = 20 x . In order to reach the point ( r, s ), we must go through either ( r − 1 , s ) or
    ( ) ( )
    s − 20( r − 1)
    s + r − 1 s − 1 − 20 r s + r − 1
    ( r, s − 1). Therefore, we have N ( r, s ) = N ( s, r − 1)+ N ( s − 1 , r ) = + =
    s + r − 1 s s + r − 1 s
    ( )
    s − 20 r s + r
    .
    s + r s
    Remark This is a special case of the ballot problem, first studied in 1887 by Joseph Bertrand, generalizing the Catalan numbers. A good expository article on this problem is “Four Proofs of the Ballot
    Problem” by Marc Renault available on his website athttp://webspace.ship.edu/msrenault/ballotproblem/ .
    In 2009, Yufei Zhao studied a variant problem called bidirectional ballot sequences, which he used toconstruct More-Sums-Then-Differences sets in additive combinatorics. His paper is available on hiswebsite athttp://web.mit.edu/yufeiz/www/mstd construction.pdf .
    Guts Round