HMMT 二月 2006 · TEAM2 赛 · 第 3 题

HMMT February 2006 — TEAM2 Round — Problem 3

[15] Prove that, given any formation, each mobot may be colored in one of three colors — say, white, black, and blue — such that no two adjacent clumps of grass are mowed by different mobots of the same color. Two clumps of grass are adjacent if the distance between them is 1. In your proof, you may use the Four-Color Theorem if you’re familiar with it.

解析

[15] Prove that, given any formation, each mobot may be colored in one of three colors — say, white, black, and blue — such that no two adjacent clumps of grass are mowed by different mobots of the same color. Two clumps of grass are adjacent if the distance between them is 1. In your proof, you may use the Four-Color Theorem if you’re familiar with it. Solution: We can divide the coordinate plane into regions: Let’s say a point belongs to Region 0 if the closest lattice point to it is not on the lawn, and each mobot M owns a region that is the set of points for which the closest lattice point is on the lawn and mowed by M . Applying the Four-Color Theorem to these regions, we note that all the conditions demanded in the problem are satisfied. In particular at most 3 colors are used on the mobots because every mobot region borders Region 0 and hence is not colored the same color as Region 0.