HMMT 二月 2013 · 团队赛 · 第 10 题
HMMT February 2013 — Team Round — Problem 10
题目详情
- [ 40 ] Chim Tu has a large rectangular table. On it, there are finitely many pieces of paper w ith non- overlapping interiors, each one in the shape of a convex polygon. At each step, Chim Tu is allowed to slide one piece of paper in a straight line such that its interior does not touch any other piece of paper during the slide. Can Chim Tu always slide all the pieces of paper o ↵ the table in finit ely many steps? HMMT 2013 Saturday 16 February 2013 Team Round 2 2 ab 1 | a b |
解析
- [ 40 ] Chim Tu has a large rectangular table. On it, there are finitely many pieces of paper with non- overlapping interiors, each one in the shape of a convex polygon. At each step, Chim Tu is allowed to slide one piece of paper in a straight line such that its interior does not touch any other piece of paper during 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 n that 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 the pieces 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 right i (i.e. in the positive x -direction). For each P let B be a bottommost (i.e. lowest y -coordinate) point on i i the boundary of P . Define a point Q to be exposed if the ray starting at Q in the positive x direction i meets the interior of no piece of paper. Consider the set of all exposed B ; this set is nonempty because certainly the bottommost of all the i B is exposed. Of this set, let B be the exposed B with maximal y -coordinate, and if there are more i k i than one such, choose the one with maximal x -coordinate. We claim that the corresponding P can k be 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 the k k k rays pointing in the positive x direction from A and B , must contain interior point(s) of some set of k k polygon(s) P in its interior. All of their bottommost points B must lie in R , since none of them can j j have 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 be k i that all of the B corresponding to the blocking P have larger y -coordinate. Now, choose of these the j j one with smallest y -coordinate - it must be exposed, and it has strictly higher y -coordinate than B , k contradiction. It follows that the interior of R intersects no pieces of paper. 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 nD 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