On a rectangular sheet of paper, several segments were drawn parallel to its sides. These segments divide the sheet into several rectangles (so that there are no parts of drawn segments inside rectangles). Petya wants to draw one of two diagonals in each of these rectangles dividing it into two triangles, and then color all triangles, each triangle either black or white. Determine if Petya can always do this so that no two triangles of the same color have a common boundary segment.
Solution
Let Petya draw a diagonal in each of the rectangles from the bottom-left corner to the top-right corner. After this, he will color all the triangles adjacent to the top-left corners of the rectangles black, and the rest — white.
Let us prove that such a coloring will work. Consider a common boundary segment of two triangles. If this segment is a diagonal, then a black triangle adjoins it from above, and a white one from below. If the segment is horizontal, then a white triangle adjoins it from above, and a black one — from below; the case of a vertical segment is similar. Therefore, such a coloring is suitable.
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.