Maths Olympiad Prep

Library / /57 of 61

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Canada

Problem:
A rectangle RR is divided into a set SS of finitely many smaller rectangles with sides parallel to the sides of RR such that no three rectangles in SS share a common corner. An ant is initially located at the bottom-left corner of RR. In one operation, we can choose a rectangle rSr \in S such that the ant is currently located at one of the corners of rr, say cc, and move the ant to one of the two corners of rr adjacent to cc.

Suppose that after a finite number of operations, the ant ends up at the top-right corner of RR. Prove that some rectangle rSr \in S was chosen in at least two operations.

Solution

Solution:
Consider the following version of the problem:
A rectangle RR is divided into a set SS of finitely many smaller rectangles such that no three rectangles in SS share a common corner. For each rSr \in S, draw two non-intersecting arcs inside rr, connecting the pairs of adjacent corners of rr (there are two ways to do this, by connecting either the horizontally or vertically adjacent corners). Prove that there does not exist a path from the bottom-left corner of RR to the top-right corner of RR by walking only along these arcs.

Figure 1
<center>Figure 1: A possible diagram of all the arcs. </center>

In this problem, consider an undirected graph where nodes correspond to corners of rectangles in SS and edges correspond to the arcs, connecting the two nodes that the arc connects. The degrees of the nodes corresponding to the corners of RR are all exactly 1. Since no three rectangles in SS share a common corner, all intersection points have a pattern like \vdash, ¬\neg, \perp, or \top, so the degree of all other nodes is exactly 2. Therefore, this graph can be decomposed into several paths and cycles. The only possible endpoints of paths are the degree 1 nodes, which are the corners of RR. It follows that if there exists a path from the bottom-left corner to the top-right corner of RR, then there also exists a path from the bottom-right corner to the top-left corner of RR. However, this is impossible because these two paths (viewed as planar curves inside RR) must intersect, which cannot occur. Therefore, this claim is proved.

Returning to the original problem, suppose some operations were performed while choosing each rectangle at most once. Draw two arcs inside every rectangle, either both horizontal if the ant used this rectangle to move horizontally or both vertical if the ant used this rectangle to move vertically (or pick one arbitrarily if this rectangle was not used). By the new version of the problem, there does not exist a path from the bottom-left corner to the top-right corner of RR, and it follows that it is impossible for the ant to have reached the top-right corner of RR, finishing the proof.

Suppose that no rectangle was chosen in at least two operations. In particular, a rectangle cannot be selected in two consecutive operations.
At any point in the process, consider whether the last move by the ant was horizontal or vertical, and whether the most recently chosen rectangle was to the left or the right of the ant's path. In the first move, either the ant moved horizontally and the rectangle was to the left, or the ant moved vertically and the rectangle was to the right. We claim that this invariant is preserved throughout the entire process (see Figure 2 for a sample path). Assuming this claim, the final move to the top right corner must select the top right rectangle. If it is vertical, this is to the left of the path, and if it is horizontal, it is to the right of the path, both of which are impossible, providing a contradiction.

Figure 2
<center>Figure 2: A possible path by the ant. The red arrows are all vertical, with the corresponding rectangle to the right. The blue arrows are all horizontal, with the corresponding rectangle to the left. </center>

It remains to show that the invariant is preserved. Since four rectangles cannot intersect at a corner, each intersection has a pattern like \vdash, ¬\neg, \perp, or \top.
First, assume the ant moves up, hence the chosen rectangle rr is on the right. The possible configurations are depicted in the first two diagrams in Figure 3.
Figure 3
<center>Figure 3: Possible ant moves going up or right. </center>

In each case, the ant must choose rectangle ss next (to avoid repeating rr twice), and we see that both side choices preserve a horizontal move with ss left, or a vertical move with ss right. By rotating the picture by 180180^{\circ}, we cover the two possibilities for the ant moving downward.
If the ant moves right, then rr must occur on the left, and the possible configurations are the last two diagrams of Figure 3. Once again, rectangle ss must be chosen next, and the invariant is similarly preserved. The case of the ant moving left is again handled by a 180180^{\circ} rotation, completing the proof.

This is a variant of Solution 2. As in that proof, assume that no rectangle was chosen in two consecutive operations. We claim that for every move, the ant is in either the bottom-left or top-right corner of the chosen rectangle, and moves to the bottom-right or top-left corner.
This is clearly true of the first move. If the ant starts at the bottom-left or top-right corner on a move (choosing rectangle rr), it is clear that they must move to the bottom-right or top-left of rr. Assume they moved to the bottom-right corner of rr, and chose rectangle ss in the next move. If they are at the bottom-right corner of ss, then rr and ss are either equal or overlap, a contradiction. If they are at the top-left of ss, then rr and ss intersect at a corner and no sides, and we must have 4 rectangles intersecting at a corner, again a contradiction.
Therefore they must be at the bottom-left or top-right corner of ss, as desired. The case where the ant is at the top-left corner of rr is analogous.
If the ant is able to make it to the top right corner, their final move must select rr as the top-right rectangle, and they move to the top-right corner, which is therefore impossible.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.