HMMT 二月 2006 · TEAM1 赛 · 第 3 题
HMMT February 2006 — TEAM1 Round — Problem 3
题目详情
- [40] In this problem, we stipulate that m ≥ n , and the lawn is shaped differently. The clumps are now at the lattice points in a trapezoid: 2 { ( x, y ) ∈ Z | 0 ≤ x < n and 0 ≤ y < m + 1 − n + x } , As in problem 2, mobots can be set to move either north or east. For given m and n , determine with proof the number of allowable formations.
解析
- [40] In this problem, we stipulate that m ≥ n , and the lawn is shaped differently. The clumps are now at the lattice points in a trapezoid: 2 { ( x, y ) ∈ Z | 0 ≤ x < n and 0 ≤ y < m + 1 − n + x } , As in problem 2, mobots can be set to move either north or east. For given m and n , determine with proof the number of allowable formations. 2 Solution: For exactly the same reasons as in problem 2, we have a one-to-one correspondence between the allowable formations and paths (going 1 unit up or right at a time) from (0 , 0) to ( n, m ) avoiding points ( x, y ) with y > m + 1 − n + x . The number of these paths equals the total number of up/right paths from (0 , 0) to ( n, m ) minus the number of up/right paths from (0 , 0) to ( n, m ) that do pass through ( ) m + n at least one point ( x, y ) with y > m + 1 − n + x . The first of these numbers is , m as before. It remains to calculate the second of these numbers. To that end, we first note that the reflection of ( n, m ) across the line y = m + 2 − n + x is ( n − 2 , m + 2). Now there is a one-to-one correspondence between up/right paths from (0 , 0) to ( m, n ) that pass through something with y ≥ m + 2 − n + x with up/right paths from (0 , 0) to ( n − 2 , m + 2): indeed, taking a path of one kind, we may isolate the first point on it that lies on the line y = m + 2 − n + x , and reflect the rest of the ( ) m + n path through that line, to obtain a path of the other kind. There are therefore m +2 paths of either kind. The answer is therefore ( ) ( ) m + n m + n − m m + 2 or, if you happen to prefer, ( m + n )! [( m + 2)( m + 1) − n ( n − 1)] . ( m + 2)! n !