返回题库

HMMT 二月 2006 · TEAM2 赛 · 第 2 题

HMMT February 2006 — TEAM2 Round — Problem 2

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. [40] Prove that the minimum number of mobots you need to mow your lawn is min { m, n } .
解析
  1. [40] Prove that the minimum number of mobots you need to mow your lawn is min { 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 toward the 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 different mobot. 1