HMMT 二月 2006 · TEAM1 赛 · 第 5 题
HMMT February 2006 — TEAM1 Round — Problem 5
题目详情
- [25] With the same lawn and the same allowable mobot orientations as in the previous problem, let ◦ us call a formation “happy” if it is invariant under 120 rotations. (A rotation applies both to the positions of the mobots and to their orientations.) An example of a happy formation for n = 2 might be ↖ → ↙ Find the number of happy formations for a given n . Polygons [110]
解析
- [25] With the same lawn and the same allowable mobot orientations as in the previous ◦ problem, let us call a formation “happy” if it is invariant under 120 rotations. (A rotation applies both to the positions of the mobots and to their orientations.) An example of a happy formation for n = 2 might be ↖ → ↙ Find the number of happy formations for a given n . Solution: If n ≡ 1 (mod 3), then there is a clump of grass at the center of the lawn; otherwise there are 3 blades of grass equally closest to the center. In the former case, whatever mobot mows this center blade of grass cannot possibly have a counterpart ◦ under a 120 rotation: if this mobot starts in the center, it must be oriented a certain way, and whatever way that is, cannot remain invariant under such a rotation; but if the mobot does not start in the center, then it will collide in the center with its ◦ counterparts under the 120 rotations. In the case that n 6 ≡ 1 (mod 3), by considering how the three central blades of grass can be mowed, we easily see that there are two possibilities, both of which involve starting one mobot at each of these three positions. Both possibilities distinctly have the effect of cutting up the rest of the lawn (i.e., the part of the lawn not mowed by any of these three mobots) into three congruent pieces. The point is that these pieces are equivalent to trapezoids as in problem 3, both in their shape, and in the allowed directions of mobot motion. Luckily, we know how to count the ways to configure each such trapezoid. Call the trapezoid defined in problem 3 an “( m, n )-trapezoid.” 2 n n − 3 2 n − 3 n If n ≡ 0 (mod 3), then these pieces are either all ( , )-trapezoids or all ( , )- 3 3 3 3 trapezoids, depending on how the central mobots are configured. In this case, the answer is (( ) ( )) (( ) ( )) 3 3 n − 1 n − 1 n − 1 n − 1 − + − . 2 n 2 n +6 2 n − 3 2 n +3 3 3 3 3 2 n − 1 n − 2 If, on the other hand, n ≡ 2 (mod 3), then these pieces are either all ( , )- 3 3 2 n − 4 n +1 trapezoids or all ( , )-trapezoids, again depending on how the central mobots 3 3 are configured. In this case, the answer is (( ) ( )) (( ) ( )) 3 3 n − 1 n − 1 n − 1 n − 1 − + − . 2 n − 1 2 n +1 2 n − 4 2 n − 2 3 3 3 3 Polygons [110]