HMMT 二月 2006 · TEAM1 赛 · 第 2 题
HMMT February 2006 — TEAM1 Round — Problem 2
题目详情
- [25] For this problem, our lawn is an m × n rectangular grid of clumps, that is, with m rows running east-west and n columns running north-south. To be even more explicit, we might say our clumps are at the lattice points 2 { ( x, y ) ∈ Z | 0 ≤ x < n and 0 ≤ y < m } . However, mobots are now allowed to be oriented to go either north or east only. So one 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 !
解析
- [25] For this problem, our lawn is an m × n rectangular grid of clumps, that is, with m rows running east-west and n columns running north-south. To be even more explicit, we might say our clumps are at the lattice points 2 { ( x, y ) ∈ Z | 0 ≤ x < n and 0 ≤ y < m } . However, mobots are now allowed to be oriented to go either north or east only. So one 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 and paths 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), so start 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 will meet another mobot, upon which you can repeat the above process, until you leave the 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 path would 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 orient that 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. Every path from (0 , 0) to ( n, m ) consists of n moves to the right and m moves up done in an ( ) ( m + n )! m + n arbitrary order, and there are precisely = orders. m m ! n !