HMMT 二月 2006 · TEAM1 赛 · 第 3 题

英文解析

3. [40] In this problem, we stipulate that m ≥ n , and the lawn is shaped differently. Theclumps are now at the lattice points in a trapezoid:
   { ( x, y ) ∈ Z | 0 ≤ x < n and 0 ≤ y < m + 1 − n + x } ,2
   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.
   Solution: For exactly the same reasons as in problem 2, we have a one-to-one 2
   correspondence between the allowable formations and paths (going 1 unit up or rightat 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 + nat least one point ( x, y ) with y > m + 1 − n + x . The first of these numbers is ,
   as before. It remains to calculate the second of these numbers.m
   To that end, we first note that the reflection of ( n, m ) across the line y = m + 2 − n + xis ( n − 2 , m + 2). Now there is a one-to-one correspondence between up/right pathsfrom (0 , 0) to ( m, n ) that pass through something with y ≥ m + 2 − n + x with up/rightpaths from (0 , 0) to ( n − 2 , m + 2): indeed, taking a path of one kind, we may isolatethe first point on it that lies on the line y = m + 2 − n + x , and reflect the rest of the
   ( )
   m + npath through that line, to obtain a path of the other kind. There are thereforem +2
   paths of either kind.
   The answer is therefore
   ( ) ( )
   m + n m + nm m + 2−
   or, if you happen to prefer,
   ( m + n )! [( m + 2)( m + 1) − n ( n − 1)]
   .
   ( m + 2)! n !