HMMT 二月 2006 · TEAM2 赛 · 第 1 题
HMMT February 2006 — TEAM2 Round — Problem 1
题目详情
(1) for exactly one of the formations does a mobot starts on that clump, or (2) there are mobots starting on this clump for both the formations, but they’re oriented in different directions. As an example, one allowable formation for m = 2, n = 3 might be as follows: · → · ↑ → ·
解析
- [25] Prove that the maximum number of mobots you need to mow your lawn is m + n − 1. Solution: This is attainable if we place one mobot at each clump in the first row, oriented north, and one mobot in the first column of each row except the first, oriented east. To show that at most m + n − 1 mobots can be used, note that each mobot must mow at least one of the m + n − 1 clumps in union of the first row and last column.