HMMT 二月 2011 · 冲刺赛 · 第 33 题
HMMT February 2011 — Guts Round — Problem 33
题目详情
- [ 25 ] Find the number of sequences consisting of 100 R ’s and 2011 S ’s that satisfy the property that among 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.
解析
- [ 25 ] Find the number of sequences consisting of 100 R ’s and 2011 S ’s that satisfy the property that among 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 11 Answer: 2111 100 Given positive integers r and s such that s ≥ 20 r , let N ( s, r ) denote the number of sequences of s copies of S and r copies of R such that for all 1 ≤ k ≤ r + s − 1, among the first k letters, the number of 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 a bijection between sequences of S ’s and R s and lattice paths from the origin to the point ( r, s ) that are 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, gener- alizing the Catalan numbers. A good expository article on this problem is “Four Proofs of the Ballot Problem” by Marc Renault available on his website at http://webspace.ship.edu/msrenault/ballotproblem/ . In 2009, Yufei Zhao studied a variant problem called bidirectional ballot sequences, which he used to construct More-Sums-Then-Differences sets in additive combinatorics. His paper is available on his website at http://web.mit.edu/yufeiz/www/mstd construction.pdf . Guts Round