HMMT 二月 2013 · 团队赛 · 第 10 题

英文解析

10. [ 40 ] Chim Tu has a large rectangular table. On it, there are finitely many pieces of paper with nonoverlapping interiors, each one in the shape of a convex polygon. At each step, Chim Tu is allowed toslide one piece of paper in a straight line such that its interior does not touch any other piece of paperduring the slide. Can Chim Tu always slide all the pieces of paper off the table in finitely many steps?
    Answer: N/A Let the pieces of paper be P , P , . . . , P in the Cartesian plane. It suffices to show
    1 2 nthat for any constant distance D , they can be slid so that each pairwise distance is at least D . Then,
    we can apply this using D equal to the diameter of the rectangle, sliding all but at most one of thepieces of paper off the table, and then slide this last one off arbitrarily.
    We show in particular that there is always a polygon P which can be slid arbitrarily far to the righti
    (i.e. in the positive x -direction). For each P let B be a bottommost (i.e. lowest y -coordinate) point oni ithe boundary of P . Define a point Q to be exposed if the ray starting at Q in the positive x directionimeets the interior of no piece of paper.
    Consider the set of all exposed B ; this set is nonempty because certainly the bottommost of all thei
    B is exposed. Of this set, let B be the exposed B with maximal y -coordinate, and if there are morei k ithan one such, choose the one with maximal x -coordinate. We claim that the corresponding P cankbe slid arbitrarily far to the right.
    Suppose for the sake of contradiction that there is some polygon blocking this path. To be precise,
    if A is the highest point of P , then the region R formed by the right-side boundary of P and thek k krays pointing in the positive x direction from A and B , must contain interior point(s) of some set ofk kpolygon(s) P in its interior. All of their bottommost points B must lie in R , since none of them canj jhave boundary intersecting the ray from B , by the construction of B .
    k k
    Because B was chosen to be rightmost out of all the exposed B with that y -coordinate, it must bek ithat all of the B corresponding to the blocking P have larger y -coordinate. Now, choose of these thej jone with smallest y -coordinate - it must be exposed, and it has strictly higher y -coordinate than B ,
    contradiction. It follows that the interior of R intersects no pieces of paper.k
    Now, for a fixed D such that D is at least the largest distance between any two points of two polygons,
    we can shift this exposed piece of paper n d to the right, the next one of the remaining pieces ( n − 1) D ,
    and so on, so that the pairwise distances between pieces of paper, even when projected onto the x -axis,
    are at least D each. We’re done.
    Team Round