HMMT 二月 2006 · TEAM1 赛 · 第 4 题

HMMT February 2006 — TEAM1 Round — Problem 4

[15] In this problem and the next, the lawn consists of points in a triangular grid of size n , so that for n = 3 the lawn looks like · · · · · · 1 ◦ ◦ 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 mobots needed to now the lawn?

解析

[15] In this problem and the next, the lawn consists of points in a triangular grid of size 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 mobots needed to now the lawn? Answer: n Solution: It is evident that n mobots are enough; just place one at the left edge of each row, and set them to move to the right. Suppose for the sake of contradiction that, for some n , it is possible to mow the lawn with fewer than n mobots. Consider the minimum n for which this is the case. Clearly n > 1. Now consider the mobot that mows the southwest corner of the lawn. This mobot is confined to either the bottom row or the left edge of the lawn; let’s assume it’s the former (the latter case is very similar). This mobot starts in the bottom row. Let’s throw it away. Now if any remaining mobots start in the bottom row, they must not be set to move east, and we may advance them by one step in the direction they’re set to go in, so that they land either off the lawn or in the second-to-last row. In doing so we have produced a starting formation of fewer than n − 1 mobots in the first n − 1 rows that will mow those rows. This contradicts the assumed minimality of n . 3