HMMT 二月 2006 · TEAM1 赛 · 第 2 题

英文解析

2. [25] For this problem, our lawn is an m × n rectangular grid of clumps, that is, with mrows running east-west and n columns running north-south. To be even more explicit,
   we might say our clumps are at the lattice points
   { ( x, y ) ∈ Z | 0 ≤ x < n and 0 ≤ y < m } .2
   However, mobots are now allowed to be oriented to go either north or east only. Soone allowable formation for m = 2, n = 3 might be as follows:
   · → ·
   ↑
   → ·
   ( m + n )!
   Prove that the number of allowable formations for given m and n is .
   m ! n !
   Solution: There is a one-to-one correspondence between allowable formations andpaths from (0 , 0) to ( n, m ) made up of n moves 1 unit to the right and m moves 1
   unit up. The correspondence works as follows: There must be a mobot at (0 , 0), sostart the path there. If that mobot is oriented to move up, then move to the right;
   if that mobot is oriented to move to the right, then move up. In doing so, you willmeet another mobot, upon which you can repeat the above process, until you leavethe lawn. Once you leave the lawn, there will be only one way to proceed to ( n, m ) —
   either keep going right, or keep going up. (For the example in the problem, our pathwould be (0 , 0)–(1 , 0)–(1 , 1)–(1 , 2)–(2 , 2)–(3 , 2).)
   Conversely, given any path from (0 , 0) to ( n, m ), we can derive back a mobot formation:
   place a mobot at every lattice point of the lawn that the path touches, and don’t orientthat mobot in the same direction as the path takes when leaving that point.
   It is easy to check that this is indeed a one-to-one correspondence as claimed. Everypath from (0 , 0) to ( n, m ) consists of n moves to the right and m moves up done in an
   ( )
   ( m + n )!
   m + narbitrary order, and there are precisely = orders.
   m m ! n !