HMMT 二月 2006 · TEAM1 赛 · 第 1 题

英文解析

1. [15] For this problem, our lawn consists of a row of n clumps of grass. This rowruns in an east-west direction. In our formation, each mobot may be oriented towardthe north, south, east, or west. One example of an allowable formation if n = 6 issymbolized below:
   ↑ ↑
   · · ←
   ↓
   (The mobot on the third clump will move westward, mowing the first three clumps.
   Each of the last three clumps is mowed by a different mobot.) Here’s another allowableformation for n = 6, considered different from the first:
   ↑ ↑
   · · ← →
   Compute the number of different allowable formations for any given n .
   Solution: Let a be the number of clumps mowed by a mobot oriented to go west,
   and let b be the number of clumps mowed by a mobot oriented to go east. (So in thetwo examples given, ( a, b ) would be (3 , 0) and (3 , 1), respectively.) We may ask howmany allowable formations with a given ordered pair ( a, b ) there are, and then sumour answers up over all possible ordered pairs ( a, b ).
   Given any particular ( a, b ), first of all, a and b had better be non-negative integerssumming to at most n . As long as that’s true, there will be n − a − b clumps of grasswhich are each mowed by a single mobot oriented to go either north or south: theren − a − b 1
   are thus 2 possibilities. So our answer isn n − a n n
   ∑ ∑ ∑ ∑
   n − a − b n − a n − a − 1 0 n − a +1
   2 = (2 + 2 + · · · + 2 ) = (2 − 1)
   a =0 b =0 a =0 a =0
   ∑nn − a +1 n +1 n n − 1 1 = − ( n + 1) + 2 = − ( n + 1) + (2 + 2 + 2 + · · · + 2 )
   a =0
   n +2 n +2 = − ( n + 1) + (2 − 2) = 2 − n − 3 .