HMMT 十一月 2014 · 团队赛 · 第 7 题
HMMT November 2014 — Team Round — Problem 7
题目详情
- [ 7 ] Sammy has a wooden board, shaped as a rectangle with length 2 and height 3 . The board is divided into a grid of unit squares. A termite starts at either the left or bottom edge of the rectangle, and walks along the gridlines by moving either to the right or upwards, until it reaches an edge opposite the one from which the termite started. Depicted below are two possible paths of the termite. The termite’s path dissects the board into two parts. Sammy is surprised to find that he can still arrange the pieces to form a new rectangle not congruent to the original rectangle. This rectangle has perimeter P . How many possible values of P are there? Hexagons
解析
- [ 7 ] Sammy has a wooden board, shaped as a rectangle with length 2 and height 3 . The board is divided into a grid of unit squares. A termite starts at either the left or bottom edge of the rectangle, and walks along the gridlines by moving either to the right or upwards, until it reaches an edge opposite the one from which the termite started. Depicted below are two possible paths of the termite. The termite’s path dissects the board into two parts. Sammy is surprised to find that he can still arrange the pieces to form a new rectangle not congruent to the original rectangle. This rectangle has perimeter P . How many possible values of P are there? ′ Answer: 4 Let R be the original rectangle and R the new rectangle which is different from R . ′ ′ We see that the perimeter of R depends on the possibilities for the side lengths of R . We will prove that the dividing line must have the following characterization: starting from the lower left corner of R , walk to the right by distance a , then walk up by distance b , for some positive number a and b , and repeat the two steps until one reaches the upper right corner of R , with the condition that the last step is a walk to the right. (The directions stated here depends on the orientation of R , but we can always orient R so as to fit the description.) Let there be n + 1 walks to the right and n walks to the top, then we have that this division would rearrange a rectangle of dimension ( n + 1) a × nb into a rectangle of dimension na × ( n + 1) b . Let us first assume the above. Now, according to the problem, it suffices to find n, a, b such that 2014 2014 2014 2014 ( n + 1) a = 2 , nb = 3 or ( n + 1) a = 3 , nb = 2 . This means that n + 1 and n are a power of 3 and a power of 2, whose exponents do not exceed 2014. This corresponds to finding nonnegative k l k l integers k, l ≤ 2014 such that | 2 − 3 | = 1. The only possible pairs of (2 , 3 ) are (2 , 1) , (2 , 3) , (3 , 4) ′ and (8 , 9). So there are 4 possible configurations of R . Now, we prove our claim. For completeness, we will actually prove the claim more generally for any cut, not just ones that move right and up (hence the length of the solution which follows, but only the above two paragraphs are relevant for the purposes of finding the answer). Team Round First we show that the dividing boundary between the two pieces must meet the boundary of R at two points, each being on opposite sides of R as the other. To see why, consider that otherwise, there would be two consecutive sides of R which belong to the same piece. Then, the smallest rectangle containing such a configuration must have each side being as large as each of the two sides, and thus ′ ′ ′ it is R . Since this piece is also part of R , R must contain R , but their areas are equal, so R = R , a contradiction. Now, let the dividing boundary go from the top side to the bottom side of R , and call the right piece ′ ”piece 1” and the left piece ”piece 2.” We orient R in such a way that piece 1 is fixed and piece 2 is ′ moved from the original position in some way to create R . We will show that piece 2 must be moved ◦ by translation by some vector v , t . Otherwise, piece 2 is affected by t as a well as a rotation by 90 v v ◦ or 180 . We show that these cases are impossible. ◦ First, consider the case where there is a 90 rotation. Let the distance from the top side to the bottom side of R be x . Then, the two pieces are contained between a pair of horizontal lines which are of ◦ distance x apart from one another. If piece 2 is rotated by 90 , then these horizontal lines become a ′ pair of vertical lines which are of distance x apart from one another. So R is contained within a union of regions between a pair of horizontal lines and a pair of vertical lines. ′ Now, we show that R must be contained within only one of these regions. Consider if there exists ′ points ( x , y ) and ( x , y ) in R such that ( x , y ) is not in the horizontal region (so that y is out 1 1 2 2 1 1 1 of range) and ( x , y ) is not in the vertical region (so that x is out of range). Then, it follows that 2 2 2 ′ ( x , y ) is also in the rectangle R . But ( x , y ) cannot be contained in either region, since both of its 2 1 2 1 x and y coordinates are out of range, a contradiction. ′ So let us assume, without loss of generality, that R is contained in the vertical region (the one which ′ contains piece 2). Then, the horizontal side of R cannot have length greater than x , the width of the region. However, piece 2 is contained in the region, and its width is exactly x . Therefore, the width of ′ R must be exactly x , rendering it to be the same shape as R , a contradiction. ◦ Next, we show that the case with a 180 rotation is also impossible. We modify our considerations from the previous case by considering a half -region of the region between a pair of horizontal lines (which are still are of distance x apart), which we define as a part of the region on the right or on the left of a certain vertical line. Then, piece 2 is contained within a certain half-region going to the ′ right and piece 1 is contained within a certain half-region going to the left . Now, in R , since piece 2 is ◦ ′ rotated by 180 , we would have both half-regions going to the left, and R is contained within a union of them. Now, consider the ”end” of each half-region (the part of the boundary that is vertical). The ends of ′ both half-regions must be contained in R , since they are part of piece 1 and piece 2. Consider a vector that maps the end of one half-region to the other. If the vector is horizontal, then the union of the regions have vertical distance x . Similarly to the previous case, we deduce that the vertical side of R ′ must be of length no more than x , and so must be exactly x , but then R = R , a contradiction. Now, if the vector has both nonzero horizontal and vertical components, then the parallelogram gen- erated by the locus of the end of a half-region being translated by the vector to the end of the other ′ ′ half-region must be contained within R (since R is convex). However, the parallelogram is not con- tained within the union of the two half-regions, a contradiction. Finally, if the vector is vertical, then the two half-regions must be on top of one another, and so will ′ ′ have no region in common. Then, since R is a rectangle, the intersection of R with each half-region ◦ will also be a rectangle. So pieces 1 and 2 must be rectangles. But then a rotation of 180 would map piece 2 to itself. So this reduces to a case of pure translation. ′ We now consider the translation t by a vector v on piece 2. Since R must contain the ends of the v ′ half-regions (which retain their original orientations), the vertical side of R must be at least of length ′ ′ x . But R 6 = R , so the vertical side of R has length strictly greater than x . This implies that the ′ horizontal side of R must be strictly shorter than that of R , since they have equal area. However, ′ the horizontal side of R is at least as long as the horizontal distance between the ends of the two half-regions, so the ends of the two half-regions must have moved closer to one another horizontally. Team Round This implies that the vector v has a positive x component. Also, v cannot be entirely horizontal, because there is no more space for piece 2 to move into. So v has a nonzero y component. Without loss of generality, let us assume that v has a positive y component. Before we continue further, let us label the vertices of R as A, B, C, D , going in counter-clockwise direction, with the left side of R being AB and the right side of R being CD . So AB is in piece 2 ′ ′ and CD is in piece 1. Call the translated piece 2 that is part of the rectangle R piece 2 , with the ′ ′ corresponding points A and B . Now, consider the half-regions of piece 1 and piece 2. They are half-regions with the end AB going ′ to the right and the one with the end CD going to the left. So, in R , the half-regions are with end ′ ′ ′ A B going to the right and with end CD going to the left, and R is contained within the union of ′ ′ ′ these two. Now, there cannot be a point in R that is to the left of A B , since the smallest rectangle ′ containing that point and A would not be contained in the union of the two half-regions. Similarly, ′ there cannot be a point in R that is to the right of CD for the same reason. These restrictions imply ′ ′ ′ that R must be contained within the union of the two half-regions that lie horizontally between A B ′ ′ and CD . However, since the smallest rectangle containing A and C is precisely this region, R must ′ ′ ′ be this region. Let A B intersect BC at L and let CD intersect the line passing through A which is ′ ′ parallel to AD at M . We have R = A LCM . ′ ′ Now, consider the segments BL and LB . We know that BL is a boundary of piece 2. Also, since LB ′ ′ ′ is a boundary of R and it is below piece 2 , it cannot be a boundary of piece 2 . Therefore, it must be ′ a boundary of piece 1. Since LB is not a boundary of R but is a boundary of piece 1, it must be part of the dividing boundary between piece 1 and 2, and so must also be a boundary of piece 2. ′ ′′ We now prove that: from a sequence of B, B , B , ... , each being translated from the preceding one by ′ ′′ v , one of them must eventually lie on AD . Also, if L, L , L , ... is also a sequence of L being successively translated by v , then, using B and L to designate the i th term of each sequence: B L and L B i i i i i i +1 must be part of the boundary of piece 2 for all i ≤ N − 1, where B is the last point, the one that lies N on AD . We have already proved the assertion for i = 1. We now set out to prove, by induction, that B L and i i L B must be part of the boundary of piece 2 for all i such that B is still within R or on the edge i i +1 i +1 of R . Consider, by induction hypothesis, that B L and L B are parts of the boundary of piece 2. i − 1 i − 1 i − 1 i ′ Then, by mapping, B L and L B must be parts of the boundary of piece 2 . Since the dividing i i i i +1 boundary of R go from top to bottom, L B cannot be on the rightmost edge of R , which is also i i +1 ′ ′ the rightmost edge of R . This means that L B is not a boundary of R . So we have that B L and i i +1 i i ′ ′ L B are not boundaries of R but are boundaries of piece 2 , so they must be boundaries of piece 1. i i +1 Now, since they are not boundaries of R either but are boundaries of piece 1, they must be boundaries of piece 2, as desired. Now we are left to show that one of B must lie exactly on AD . Let B be the last term of the sequence i i that is contained within R or its boundary. Then, by the previous result, B L and L B are i − 1 i − 1 i − 1 i ′ boundaries of piece 2. Then, by mapping, B L is a boundary of piece 2 . Since B L is on or below i i i i ′ ′ AD , it cannot be on the boundary of R , but since it is a boundary of piece 2 , it must also a boundary of piece 1. Now, if B is not on AD , then B L will not be a boundary of R , but since it is a boundary i i i of piece 1, it must also be a boundary of piece 2. By mapping, this implies that B L must be a i +1 i +1 ′ boundary of piece 2 . However, B L is not contained within R or its boundary, and so cannot be i +1 i +1 ′ on piece 1’s boundary. Therefore, since B L is a boundary of piece 2 but not of piece 1, it must i +1 i +1 ′ ′ be a boundary of R . This means that B L is on the upper edge of R . Mapping back, we get i +1 i +1 that B L must be on the upper edge of R , a contradiction to the assumption that B is not on AD i i i (the upper edge of R ). So B is on AD , as desired. i Let B be the term of the sequence that is on AD . We have now shown that N L B , B L , . . . , B L , L B 1 2 2 2 N − 1 N − 1 N − 1 N completely defines the dividing line between piece 1 and piece 2. Moreover, B = B , defining the 1 starting point of the dividing line. We now add the final description: L = D . To see why, note that N Team Round L must be on the upper edge of R , as it is in the same horizontal level as B . However, since L N N N − 1 is one of furthest points to the right of piece 2, by mapping, L must be one of the furthest points to N ′ ′ the right of piece 2 , and so must be on the rightmost edge of piece 2 , which is the rightmost edge of ′ R and of R . Therefore, L is on the upper edge and the rightmost edge of R , and so it must be D , N as desired.