There is a board divided into unit squares, and we have drawn one of the two diagonals of each unit square. Prove that there is a path using only these diagonals that either connects the upper side of the board to the lower side or connects the left side of it to the right side.
Solution
A connected component of diagonals is some of the diagonals that are connected to each other by a path of diagonals, and if we add another diagonal to it, it will no longer be connected. Easily, it can be seen that the diagonals that are not in this component but are on the border of this component, are connected. (until they don't cross the table sides.)
Now, consider a path of diagonals that starts from the upper side of the table and has the maximum height among all the paths starting from the upper side. If the height of this path be , the problem is solved, otherwise suppose that the height be less than . Consider the connected component having this path. If this component is not connected to the right side of the table, then its rightmost border's height will be more, and this is a contradiction. Similarly if this connected component is not connected to the left side of the table, then its leftmost border's height will be more, and a contradiction. Thus, this connected component is connected to both right and left sides of the table, and hence they're connected to each other.
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.