HMMT 二月 2006 · TEAM1 赛 · 第 5 题

英文解析

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. (Arotation applies both to the positions of the mobots and to their orientations.) Anexample 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 certainway, and whatever way that is, cannot remain invariant under such a rotation; butif 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 grasscan be mowed, we easily see that there are two possibilities, both of which involvestarting one mobot at each of these three positions. Both possibilities distinctly havethe effect of cutting up the rest of the lawn (i.e., the part of the lawn not mowed byany of these three mobots) into three congruent pieces. The point is that these piecesare equivalent to trapezoids as in problem 3, both in their shape, and in the alloweddirections of mobot motion. Luckily, we know how to count the ways to configure eachsuch 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, theanswer 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]