HMMT 二月 2006 · TEAM1 赛 · 第 1 题
HMMT February 2006 — TEAM1 Round — Problem 1
题目详情
- [15] For this problem, our lawn consists of a row of n clumps of grass. This row runs in an east-west direction. In our formation, each mobot may be oriented toward the north, south, east, or west. One example of an allowable formation if n = 6 is symbolized 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 allowable formation for n = 6, considered different from the first: ↑ ↑ · · ← → Compute the number of different allowable formations for any given n .
解析
- [15] For this problem, our lawn consists of a row of n clumps of grass. This row runs in an east-west direction. In our formation, each mobot may be oriented toward the north, south, east, or west. One example of an allowable formation if n = 6 is symbolized 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 allowable formation 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 the two examples given, ( a, b ) would be (3 , 0) and (3 , 1), respectively.) We may ask how many allowable formations with a given ordered pair ( a, b ) there are, and then sum our 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 integers summing to at most n . As long as that’s true, there will be n − a − b clumps of grass which are each mowed by a single mobot oriented to go either north or south: there 1 n − a − b are thus 2 possibilities. So our answer is n 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 n ∑ n − 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 .