HMMT 二月 2006 · TEAM2 赛 · 第 5 题
HMMT February 2006 — TEAM2 Round — Problem 5
题目详情
- [40] For n, m ≥ 3, prove that a formation has exactly six possible colorings satisfying the conditions in problem 3 if and only if there is a mobot that starts at (1 , 1). Polygons [130]
解析
- [40] For n, m ≥ 3, prove that a formation has exactly six possible colorings satisfying the conditions in problem 3 if and only if there is a mobot that starts at (1 , 1). Solution: Let’s trace a path through all the mobots. There must be a mobot at (0 , 0), so start the path there. If that mobot is oriented to move up, then move to the right; if that mobot is oriented to move to the right, then move up. In doing so, you will meet another mobot, upon which you can repeat the above process, until you leave the lawn. In tracing this path, we’ve effectively ordered the mobots, starting with (0 , 0). At any point in this ordering, we have a number of choices for how to color the current mobot without violating the condition with any previously colored mobot. Specifically, there are three ways to color the mobot at (0 , 0). If a mobot has x - or y -coordinate 0, there are 2 ways to color it: it need only not be the same color as the previous mobot on our trail. If a mobot has both x - and y -coordinates positive, then there is only 1 way to color it: it cannot be the same color as whatever mobots mows the clump directly south or directly west of its starting point. Thus, if there is a mobot at (1 , 1), our path must begin with either (0 , 0)–(0 , 1)–(1 , 1) or (0 , 0)–(1 , 0)–(1 , 1), and in either case there are only 6 ways to do the coloring. Otherwise, if there is no mobot at (1 , 1), our path must begin with either (0 , 0)–(0 , 1)– (0 , 2) or (0 , 0)–(1 , 0)–(2 , 0), and in either case there are already 3 × 2 × 2 = 12 ways to do the coloring thus far. Polygons [130]