HMMT 二月 2017 · COMB 赛 · 第 10 题

英文解析

10. Compute the number of possible words w = w w . . . w satisfying:
    1 2 100
    • w has exactly 50 A ’s and 50 B ’s (and no other letters).
    • For i = 1 , 2 , . . . , 100, the number of A ’s among w , w , . . . , w is at most the number of B ’s among
    1 2 iw , w , . . . , w .
    1 2 i
    • For all i = 44 , 45 , . . . , 57, if w is an B , then w must be an B .
    i i +1
    Proposed by: Allen Liu
    Call the last property in the problem statement P ( i, j ) where in the statement i = 44, j = 57. We showthat the number of words satisfying the first two conditions and P ( m, m + k ) is the same independentof m (assuming k is fixed). It suffices to show that the number of words satisfying P ( m − 1 , m + k − 1)
    is the same as the number of words satisfying P ( m, m + k ). Construct a bijection as follows: for aword satisfying P ( m − 1 , m + k − 1), if it satisfies P ( m, m + k ), leave it as is. Otherwise, the characterin position m + k must be B and the character in position m + k + 1 must be A . In this case, movethese two characters to positions m − 1, m (shifting all other characters back). It is not difficult toverify that this is indeed a bijection.
    Thus, the problem is now equivalent to computing the number of words satisfying the first two conditions and P (1 , 14). However, this condition simply means that the first 15 characters must be B . Nowwe are essentially counting the number of paths from (15 , 0) to (50 , 50) that don’t go above y = x .
    There is a bijection between paths from (15 , 0) to (50 , 50) that do cross y = x and paths from (15 , 0)
    ( ) ( )
    85 85
    to (49 , 51) (using the standard reflection argument). Thus the answer is −
    35 34