HMMT 二月 2006 · TEAM1 赛 · 第 4 题

英文解析

4. [15] In this problem and the next, the lawn consists of points in a triangular grid ofsize n , so that for n = 3 the lawn looks like
   ·
   · ·
   · · ·
   ° °
   Mobots are allowed to be oriented to the east, 30 west of north, or 30 west of south.
   Under these conditions, for any given n , what is the minimum number of mobotsneeded to now the lawn?
   Answer: n
   Solution: It is evident that n mobots are enough; just place one at the left edge ofeach row, and set them to move to the right. Suppose for the sake of contradictionthat, for some n , it is possible to mow the lawn with fewer than n mobots. Considerthe minimum n for which this is the case. Clearly n > 1. Now consider the mobotthat mows the southwest corner of the lawn. This mobot is confined to either thebottom row or the left edge of the lawn; let’s assume it’s the former (the latter case isvery similar). This mobot starts in the bottom row. Let’s throw it away. Now if anyremaining mobots start in the bottom row, they must not be set to move east, andwe may advance them by one step in the direction they’re set to go in, so that theyland either off the lawn or in the second-to-last row. In doing so we have produced astarting formation of fewer than n − 1 mobots in the first n − 1 rows that will mowthose rows. This contradicts the assumed minimality of n . 3