HMMT 二月 2017 · COMB 赛 · 第 10 题
HMMT February 2017 — COMB Round — Problem 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 i w , 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
解析
- 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 i w , 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 show that the number of words satisfying the first two conditions and P ( m, m + k ) is the same independent of 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 a word satisfying P ( m − 1 , m + k − 1), if it satisfies P ( m, m + k ), leave it as is. Otherwise, the character in position m + k must be B and the character in position m + k + 1 must be A . In this case, move these two characters to positions m − 1, m (shifting all other characters back). It is not difficult to verify that this is indeed a bijection. Thus, the problem is now equivalent to computing the number of words satisfying the first two condi- tions and P (1 , 14). However, this condition simply means that the first 15 characters must be B . Now we 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