HMMT November, 2014

Solution:

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 \times n b$ into a rectangle of dimension $n a \times (n+1) b$.

Let us first assume the above. Now, according to the problem, it suffices to find $n, a, b$ such that $(n+1)a = 2^{2014}, n b = 3^{2014}$ or $(n+1)a = 3^{2014}, n b = 2^{2014}$. 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 integers $k, l \leq 2014$ such that $|2^{k} - 3^{l}| = 1$. The only possible pairs of $(2^{k}, 3^{l})$ 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).

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_{v}$. Otherwise, piece 2 is affected by $t_{v}$ as well as a rotation by $90^{\circ}$ or $180^{\circ}$. We show that these cases are impossible.

First, consider the case where there is a $90^{\circ}$ 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^{\circ}$, 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_{1}, y_{1})$ and $(x_{2}, y_{2})$ in $R'$ such that $(x_{1}, y_{1})$ is not in the horizontal region (so that $y_{1}$ is out of range) and $(x_{2}, y_{2})$ is not in the vertical region (so that $x_{2}$ is out of range). Then, it follows that $(x_{2}, y_{1})$ is also in the rectangle $R'$. But $(x_{2}, y_{1})$ cannot be contained in either region, since both of its $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^{\circ}$ 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^{\circ}$, 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 generated 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 contained 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^{\circ}$ would map piece 2 to itself. So this reduces to a case of pure translation.

We now consider the translation $t_{v}$ by a vector $v$ on piece 2. Since $R'$ must contain the ends of the half-regions (which retain their original orientations), the vertical side of $R'$ must be at least of length $x$. But $R' \neq 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.

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'', \ldots$, each being translated from the preceding one by $v$, one of them must eventually lie on $AD$. Also, if $L, L', L'', \ldots$ is also a sequence of $L$ being successively translated by $v$, then, using $B_{i}$ and $L_{i}$ to designate the $i$th term of each sequence: $B_{i}L_{i}$ and $L_{i}B_{i+1}$ must be part of the boundary of piece 2 for all $i \leq N-1$, where $B_{N}$ is the last point, the one that lies on $AD$.

We have already proved the assertion for $i=1$. We now set out to prove, by induction, that $B_{i}L_{i}$ and $L_{i}B_{i+1}$ must be part of the boundary of piece 2 for all $i$ such that $B_{i+1}$ is still within $R$ or on the edge of $R$.

Consider, by induction hypothesis, that $B_{i-1}L_{i-1}$ and $L_{i-1}B_{i}$ are parts of the boundary of piece 2. Then, by mapping, $B_{i}L_{i}$ and $L_{i}B_{i+1}$ must be parts of the boundary of piece $2'$. Since the dividing boundary of $R$ go from top to bottom, $L_{i}B_{i+1}$ cannot be on the rightmost edge of $R$, which is also the rightmost edge of $R'$. This means that $L_{i}B_{i+1}$ is not a boundary of $R'$. So we have that $B_{i}L_{i}$ and $L_{i}B_{i+1}$ are not boundaries of $R'$ but are boundaries of piece $2'$, so they must be boundaries of piece 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_{i}$ must lie exactly on $AD$. Let $B_{i}$ be the last term of the sequence that is contained within $R$ or its boundary. Then, by the previous result, $B_{i-1}L_{i-1}$ and $L_{i-1}B_{i}$ are boundaries of piece 2. Then, by mapping, $B_{i}L_{i}$ is a boundary of piece $2'$. Since $B_{i}L_{i}$ is on or below $AD$, it cannot be on the boundary of $R'$, but since it is a boundary of piece $2'$, it must also be a boundary of piece 1. Now, if $B_{i}$ is not on $AD$, then $B_{i}L_{i}$ will not be a boundary of $R$, but since it is a boundary of piece 1, it must also be a boundary of piece 2. By mapping, this implies that $B_{i+1}L_{i+1}$ must be a boundary of piece $2'$. However, $B_{i+1}L_{i+1}$ is not contained within $R$ or its boundary, and so cannot be on piece 1's boundary. Therefore, since $B_{i+1}L_{i+1}$ is a boundary of piece $2'$ but not of piece 1, it must be a boundary of $R'$. This means that $B_{i+1}L_{i+1}$ is on the upper edge of $R'$. Mapping back, we get that $B_{i}L_{i}$ must be on the upper edge of $R$, a contradiction to the assumption that $B_{i}$ is not on $AD$ (the upper edge of $R$). So $B_{i}$ is on $AD$, as desired.

Let $B_{N}$ be the term of the sequence that is on $AD$. We have now shown that
$$L_{1}B_{2}, B_{2}L_{2}, \ldots, B_{N-1}L_{N-1}, L_{N-1}B_{N}$$
completely defines the dividing line between piece 1 and piece 2. Moreover, $B_{1} = B$, defining the starting point of the dividing line. We now add the final description: $L_{N} = D$. To see why, note that $L_{N}$ must be on the upper edge of $R$, as it is in the same horizontal level as $B_{N}$. However, since $L_{N-1}$ is one of furthest points to the right of piece 2, by mapping, $L_{N}$ must be one of the furthest points to 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_{N}$ is on the upper edge and the rightmost edge of $R$, and so it must be $D$, as desired.