HMMT 二月 2006 · TEAM2 赛 · 第 2 题

英文解析

2. [40] Prove that the minimum number of mobots you need to mow your lawn ismin { m, n } .
   Solution: This is attainable if we place one mobot at each clump in the first column,
   oriented toward the east, or one mobot at each clump in the last row, oriented towardthe north (whichever of the two is more efficient).
   To show that at least min { m, n } mobots must be used, note that each of the clumps
   (0 , 0), (1 , 1), (2 , 2), . . . , (min { m, n } − 1 , min { m, n } − 1) must be mowed by a differentmobot. 1