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 onthis 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.
解析
英文解析
- [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, orientedeast.
To show that at most m + n − 1 mobots can be used, note that each mobot must mowat least one of the m + n − 1 clumps in union of the first row and last column.