It was also India TST

Let $\mathcal{R}$'s dimensions be $m$ and $n$, with $m$ and $n$ odd. Label the square $(x,y)$ with $A$ if $x \equiv y \equiv 1 \bmod{2}$, $B$ if $x \equiv y \equiv 0 \bmod{2}$, and $C$ if $x \not \equiv y \bmod{2}$. Then a rectangle satisfies the problem's condition iff all of its corners are labeled with $A$ or all of them are labeled with $B$. Notice that because $m$ and $n$ are odd, there exists one less square labeled $C$ than the total number of squares labeled $A$ of $B$, and thus there must exist at least one small rectangle in which more squares are labeled $A$ or $B$. But this is easily seen to imply that all four corners of the rectangle are labeled $A$ or $B$.

Edit: made a really dumb mistake.

jdevine wrote: There's a much easier way to do this than with colouring arguments.

There's a reason why everyone else is using coloring arguments - your solution proves a weaker statement than the problem. You've proven that a rectangle with both odd dimensions exists, and an odd dimension ensures that the opposite distances have equal parity, but you haven't shown that the parity of the distances in the two different axes are equal, i.e. you could have a rectangle that is an odd distance from the top and the bottom, but an even distance from the left and the right.

This problem was proposed by oneplusone.

jdevine wrote: There's a much easier way to do this than with colouring arguments. Consider the length of $\mathcal{R}$. Since it's odd, we let it be $2n+1$. Consider a smaller rectangle $\mathcal{S}$. Let the distance from the left side of $\mathcal{S}$ to the left side of $\mathcal{R}$ be $a$, and let the distance from the right side of $\mathcal{S}$ to the right side of $\mathcal{R}$ be $b$. Iff $a$ and $b$ are the same parity, then $a+b$ is even and so $2n+1-a-b$ is odd. Repeat in the other direction (up and down instead of left and right). This means that we want to prove that there exists a rectangle whose sides are of odd length. Suppose, for sake of contradiction, that there isn't one. Then all the small rectangles have even area, but the large rectangle has an odd area. Contradiction. I'm not sure why they put that on the IMO shortlist... it would have been much more suitable in something like this and would have been a really good problem to put in, probably near the end of the paper. Naah, that doesn't quite work. You have only established the existence of a rectangle $S$ whose sides are of odd length. But $S$ might have odd distances to the northern and southern side of $\cal R$, and even distances to the eastern and western side of $\cal R$.

By induction on chessboard polygons, it is easy to show that each rectangle in such a tiling can be indexed with vertices as lattice points. Now for each rectangle of area $A$ apply the following operation. For $A \equiv 0 \pmod{2}$ tile it with dominoes and for $A \equiv 1\pmod{2}$ mark the leftmost corner and tile the remaining rectangle with dominoes. Observe that each tiling $\mathcal{T}$ maps to a tiling $\mathcal{T}’$ consisting only of dominoes and boxes such that $\mathcal{T}$ has a desired rectangle iff $\mathcal{T}’$ does. Apply chessboard colouring with upper left corner coloured red. For $\mathcal{T}’$ notice that any box placed at red square is desired. If not then all such red squares are covered in dominoes. Since no domino contains two monochrome squares and we have more red squares, we get the desired contradiction.

test20 wrote: jdevine wrote: There's a much easier way to do this than with colouring arguments. Consider the length of $\mathcal{R}$. Since it's odd, we let it be $2n+1$. Consider a smaller rectangle $\mathcal{S}$. Let the distance from the left side of $\mathcal{S}$ to the left side of $\mathcal{R}$ be $a$, and let the distance from the right side of $\mathcal{S}$ to the right side of $\mathcal{R}$ be $b$. Iff $a$ and $b$ are the same parity, then $a+b$ is even and so $2n+1-a-b$ is odd. Repeat in the other direction (up and down instead of left and right). This means that we want to prove that there exists a rectangle whose sides are of odd length. Suppose, for sake of contradiction, that there isn't one. Then all the small rectangles have even area, but the large rectangle has an odd area. Contradiction. I'm not sure why they put that on the IMO shortlist... it would have been much more suitable in something like this and would have been a really good problem to put in, probably near the end of the paper. Naah, that doesn't quite work. You have only established the existence of a rectangle $S$ whose sides are of odd length. But $S$ might have odd distances to the northern and southern side of $\cal R$, and even distances to the eastern and western side of $\cal R$. Oh... I thought it was way too easy for IMO shortlist...

MarkBcc168 wrote: A rectangle $\mathcal{R}$ with odd integer side lengths is divided into small rectangles with integer side lengths. Prove that there is at least one among the small rectangles whose distances from the four sides of $\mathcal{R}$ are either all odd or all even. Don't know, but I feel like I have seen this problem long ago. EDIT: No, it wasn't this one, it was the following theorem: Theorem: If a rectangle can tiled with rectangles, each of which have at least one side of integeral length, then the rectangle which was tiled also has at least one side of integeral length.

I discovered this problem when I was trying to solve the problem "there exists only finitely many ways to divide a rectangle into smaller rectangles of equal area". A subproblem is that there is no smooth deformation of the smaller rectangles that preserves all their area (turns out there is a completely different elegant proof for this). A slightly stronger statement is that if we perturb each edge slightly up/down or left/right, there is a rectangle that strictly contains its original form, or is strictly contained in its original form. This is equivalent to this C1. I was hoping to find some kind of "Brouwer fixed-pt" solution, but couldn't find one. My original solution is to colour the rectangle black/white in a checkerboard manner, with the 4 corners black, then it suffices to find a smaller rectangle with 4 black corners. We count the number of black and white corners among all the rectangles. For each corner vertex that is not the corner of $\mathcal{R}$, there are an equal number of black and white rectangle corners at that vertex. So there are more black corners than white, hence there is a smaller rectangle with at least 3 black corners. But a rectangle with 3 black corners necessarily has the 4th corner black.

ugh this took way too long, but I suck at combo anyways.... Call $(i,j)$ white if $2\mid i-j$, and call it black otherwise. We wish to show the existence of a rectangle with all white corners. However, a rectangle has all white corners if and only if it has more white squares than black squares. But since $\mathcal{R}$ has more whites than blacks, by PHP we are done. Remark: In my "defense", for most of the time I was trying to show that the number of all white cornered squares was odd (this is the usual strategy), but experimentation very quickly reveals this to be FALSE. Therefore, everything I was trying beforehand was bound to fail. But I was too lazy to actually experiment till the very end. Lesson: experiment One more remark: oneplusone wrote: My original solution is to colour the rectangle black/white in a checkerboard manner, with the 4 corners black, then it suffices to find a smaller rectangle with 4 black corners. We count the number of black and white corners among all the rectangles. For each corner vertex that is not the corner of $\mathcal{R}$, there are an equal number of black and white rectangle corners at that vertex. So there are more black corners than white, hence there is a smaller rectangle with at least 3 black corners. But a rectangle with 3 black corners necessarily has the 4th corner black. I think this solution needs slight rewording since $1\times x$ squares have at most 2 corners.

I need some clarification. Are the rectangles in a grid? I mean, does the large rectangle have rows and columns which intersect to make the smaller rectangles, or are the small rectangles independent? In other words, if there is a rectangle $PQRS$, will $QR$ be the side of one other small rectangle as well?

Official solution

Could someone check this please? (since > 50% of my posts contain errors) The following solution does not use coloring. Call a division of $\mathcal R$ into smaller rectangles as in the problem bad if no rectangle is of even distance to all sides. Note that by shifting side of a rectangle by $2$ units in some direction preserves badness as long as there are no other sides blocking the movement, even if the side becomes overlapped with the side of another rectangle in which case this other rectangle disappears. We can push the sides of the big rectangle this way as well. By doing such adjustment finitely many times, we get a situation in which all small rectangles are unit squares, in which case the result is evident.

Here is a solution based on another idea - a graph theory style, which is a bit clumsy here, but nevertheless, may be useful. This approach was also used in series of contest problems If $R_0$ is a rectangle satisfying the condition, it follows the sides of $R_0$ are both odd. So, there must exist an "odd" tiling rectangle. Btw, the last sentence is itself a competition problem, given somewhere. But finding such "odd" rectangle is not enough. Additionally, the coordinates of its bottom-left corner with respect to the bottom-left corner of $ R$, must be both of equal parity. Now, we consider a graph $ G$ with vertices - the corners of all tiling rectangles. For a rectangle $ABCD$, which has an even side, let it be $ AB$, we connect $A, B$ and $C,D$. But if the two sides of $ABCD$ are even, we make the edges only two of them ($A,B$ and $C,D$). One may imagine the "odd" rectangles are cut off the table. Note that some vertices of $G$ may be connected with two edges - e.g. if two rectangles share a common side. Thus, we count edges with their multiplicity. All vertices of $G$ have even degrees, except the vertices of $R$, which are of odd or zero degree, and the vertices of the cut off ("odd") rectangles, which may be odd. A corner of $R$ has zero degree exactly if it is a corner of a cut-off rectangle. A corner of a cut-off rectangle has odd degree if there are odd numbers of cut-off rectangles with that same corner. If either the bottom left or top right corner of $R$ has zero degree, we are done, since there is a cut-off rectangle with a corner there. So, suppose both of them are non isolated. We start a walk from the bottom left vertex of $R$ (from the point $A$; blue color in the attachment) and keep walking an Eulerian path while possible. Any edge of that walk has an even length. Thus, it's not possible the walk to end up in some other corner of $R$ without hitting some cut-off rectangle (btw, it proves, there exists such one). On the other hand, if we hit some cut-off rectangle in its bottom-left or top-right corner, we are done. So, suppose we end up in a corner of some cut-off rectangle, say, its top-left corner. Then we start again the walk from its bottom-right corner if it has odd degree. In case its degree is even, it means there is another cut-off rectangle incident with that vertex. If the vertex coincides with the bottom-left or top-right corner of that other rectangle, we are done, otherwise we continue the walk from its opposite corner. In the places where the walk breaks, the vector of the jump has its both coordinates odd, or even (if we jump over two, or even number of rectangles). Thus, the only possibility where the walk ends up, is the top-right corner of $R$. Now, we start another walk from the top-left corner of $R$ (point $B$ on the picture, green color). The two walks, blue and green, cannot meet (for parity reasons). But at some moment they must hit the same cut-off rectangle, which is also impossible for parity reasons. Thus, the blue walk must hit a cut-off rectangle in its bottom-left or top-right rectangle, which proves the result.

Fantastic blog post, by the way! I'm having trouble seeing why there is a contradiction if the blue and green walks use the same cut-off rectangle, since the blue one only uses vertices with coordinates of the same parity, while the green one uses vertices of different parity, so since the cut-off rectangles are odd by odd I can't see why there is a problem.

Let $C$ be the top-right vertex of the big rectangle, and $D$ - its bottom-right. Denote also as $Q$ the last cut-off rectangle, both blue and green walks meet. In the picture, it's the cut-off rectangle near $A$. Consider the following walks. 1) Blue walk from $A$ to $C$. 2) Green walk from $B$ to $D$. 3) Blue walk from $A$ to $Q$, then green walk to $B$. 4) Blue walk from $A$ to $Q$, then green walk to $D$. At least one of them fails parity check. In the picture, it's is the $4$-th walk. It becomes forky to consider all those possibilities, that's why it's a clumsy solution, only presented because of the method used.

Please check my solution and grade it (if possible)

Sol(By Jason):- Let the rectangle have dimensions $m \cdot n$. $m$ and $n$ are both odd according to problem. Color these $mn$ squares same as that of chessboard such that all its corner squares have black color. Each rectangle belongs to $1$ out of these $3$ types classified on basis of their corner squares $A$- $4$ black (so this rectangle has more blacks than whites) $B$- $2$ white, $2$ black (so this rectangle has an equal number of black and white) $C$- $4$ white (so this rectangle has more whites than blacks) Since rectangle R belongs to category $A$ it has more black squares than white. So there exists a small rectangle inside $R$ belonging to $A$ since otherwise the no. of white squares would exceed black. Note that this rectangle satisfies the problem condition.So done.

This was also Hungarian TST 2018, 2nd round. My solution was about the same as MarkBcc168's, chessboard tiling solves it fast

Does this solution work without coloring Sketch: Assume such a rectangle does not exist. There must be at least 1 rectangle with odd side lengths, otherwise the side lengths of R can not be odd. This rectangle has to have a distance of equal polarity from the top and bottom, and left and right, so the distances from top and bottom and left and right. have to be different polarity, WLOG the distance from the left and right is odd and top and bottom is even. Since the distance from the left and right are both odd, each distance must contain an odd segment. Consider the closest segment from the left that is odd to the original odd segment. Since there are no odd segments in between them, the distance between them is even. Notice that the distance from the left is equal to the distance from the left of this new segment, plus the length of the new segment, plus the length of the distance between this segment and the original odd segment. The length of the segment is odd and the distance between the 2 segments is even, which forces the distance between the new segment and the left to be even. Now the rectangle using this new segment and the original top and bottom segment works. Use. the drawing for reference.

Note that $\mathcal{G}$ has odd side lengths. We use the following lemma. Claim: For a rectangulr grid with odd side lengths, the checkerboard shading containing the corners has an odd number of squares. Proof. Follows inductively. $\blacksquare$ Now take that shading of $\mathcal{G}$ which has an odd number of squares. Any rectangle with even area covers an even number of squares. Using the lemma, for a rectangle with odd area the parity of the number of squares covered is one if and only if the corners of the rectangle are covered. Thus, there must be some rectangle $R$ with odd area and corners in the shading. It can be seen that this is the desired rectangle.

WTF this is such an elegant problem Color the rectangle black and white such that the corners are all black. Clearly, a small rectangle that satisfies the parity condition must have all black corners - equivalently, it has one more black square than white square. Other rectangles either contain an equal number of black squares and white squares, or more white squares than black. Since the large rectangle contains more black squares than white squares, we must have a small rectangle that satisfies the parity condition.

Nice problem.

noppi_kun wrote: Each small rectangle must have an even area, and therefore $\mathcal{R}$ must also have an even area, which is a contradiction. I believe this idea is correct, but there is no one else doing the same. Can someone please tell me if this is right or wrong If a rectangle has odd area, we know for sure that the distance from the vertical sides of this rectangle to $\mathcal R$ are both even or odd; we also know for sure that the distance from the horizontal sides of this rectangle to $\mathcal R$ are both even or odd; however, we do not know that all four parities are the same.

ihatemath123 wrote: noppi_kun wrote: Each small rectangle must have an even area, and therefore $\mathcal{R}$ must also have an even area, which is a contradiction. I believe this idea is correct, but there is no one else doing the same. Can someone please tell me if this is right or wrong If a rectangle has odd area, we know for sure that the distance from the vertical sides of this rectangle to $\mathcal R$ are both even or odd; we also know for sure that the distance from the horizontal sides of this rectangle to $\mathcal R$ are both even or odd; however, we do not know that all four parities are the same. I was wrong.. Thanks.

Same as above. Here is my motivation for the coloring. If the rectangle is $[0,a]\times [0,b]$ and we are considering $[x,x+c]\times [y,y+d]$, we wish to prove $c$, $d$ are odd and $x\equiv y\pmod 2$ is possible. Let us just focus on the first half. We can note that by weighting each cell by $1$, we see $\sum cd$ must be odd, so there must be some rectangle with $cd$ odd. We can then think of doing a similar thing with $x\equiv y \pmod 2$. It is quite natural to think of labeling each $(x,y)$ with $x+y$. However, we see this does not work. Then, our next idea is to label each $(x,y)$ with $\delta(x+y\equiv 0\pmod 2)$, which works.

Fun combo Tile the grid like a checkerboard with corners shaded. We can observe that a small rectangle works iff its corners are all shaded, or in other words it has one more shaded squares than non shaded squares. Now since the sum of the areas of the rectangles inside $\mathcal{R}$ is odd. There must exist an odd by odd rectangle. If all odd rectangles had blank corners then, there would be more blank squares total than shaded squares, however the rectangle has more shaded squares a contradiction. So there must exist at least one among the small rectangles whose distances from the four sides of $\mathcal{R}$ are either all odd or all even.

Color the cells of the grid black and white in checkerboard pattern so that it has $4$ black corners. Iff the rectangle's distances from the four sides are all odd or all even, then it has $4$ black corners. Assume FTSOC that we do not use any rectangle with $4$ black corners in our dissection. Then we can only use rectangles with $2$ white and $2$ black corners, or $4$ white corners. In both cases, there are at least as many white squares as black squares, but in $\mathcal G$, we have more black squares than white squares. This is a contradiction, as desired.

Checkerboard tiling, with white at the corners. Clearly some rectangle must have white squares than black corners, if the rectangle has even area it is forced to be evenly split between white and black, so it is odd and all four corners are white. Taking distances from the white corners (every two adjacent directions have the same parity, so they all have the same parity) finishes.

Solution with the following flavortext: Quote: A rectangular grid $\mathcal G$ has an odd number of square unit cells. The grid is dissected along its gridlines into several rectangles (with sides parallel to the grid). Prove that one of the rectangles $R$ in the dissection has the following property: the distance from $R$ to the four sides of $\mathcal G$ are either all odd or all even. Color the unit squares of $\mathcal G$ in a chessboard fashion, with the bottom-left square being black.For a rectangle $ \mathcal R \in \mathcal G$, define $B(\mathcal R)$ to be the number of black squares contained in it, and $W(\mathcal G)$ to be the number of white squares in it. Then the condition on our required rectangle $R$ is equivalent to $B(R) > W(R)$. So assume $B(R) \le W(R)$ for every rectangle. Then $$B(G) = \sum_{R \in P} B(R) \le \sum_{R \in P} W(R) = W(G),$$where $G$ refers to the rectangle covering the entire of $\mathcal G$, and $P$ refers to the partition. But this is impossible due to $G$ itself satisfying that $B(G) > W(G)$, contradiction. $\square$

Checkerboard color the grid using black and white, where the corners are colored black. Notice a desired rectangle $R$ is equivalent to having odd dimensions and black corners, which must exist as there are more black squares than white squares in the grid. $\blacksquare$

Color the rectangle like a chessboard with alternating black and white colors, with the corners being black. If the desired result is not true, clearly each rectangle either has an equal amount of black and white squares, or one more white compared to black. Summing this up, it follows that the number of white squares is at least the number of black squares in the entire board, which is clearly a contradiction. QED