Shapovalov A.V.

Inside a rectangular sheet of paper, $n$ rectangular holes with sides parallel to the edges of the sheet have been cut out. What is the smallest number of rectangular pieces into which this perforated sheet can be guaranteed to be cut? (The holes do not overlap and do not touch.)
Evaluation. Let's assume that one of the sides of the sheet is vertical. Along each vertical "side" of one of the holes, we will draw a vertical cut to the "limit" at the horizontal side of the adjacent hole or to the edge of the sheet. We will repeat this procedure for all holes (see the left figure). After this, the sheet will "break" into some number \( m \) of rectangles (indeed, all angles of the resulting parts are right angles).

Each rectangle has four corners, so the total number of corners of all rectangles is \( 4m \). On the other hand, to the four corners of the original sheet, each of the \( 2n \) cuts adds no more than six right angles (see the left figure, some angles formed by a certain cut may coincide with angles formed by other cuts), so the number of corners does not exceed \( 12n + 4 \).

Thus, \( 4m \leq 12n + 4 \), which means \( m \leq 3n + 1 \).

![](https://cdn.mathpix.com/cropped/2024_05_06_08342b966a7aba566077g-12.jpg?height=494&width=1780&top_left_y=2028&top_left_x=139)

Example. Arrange \( n \) holes as shown in the right figure (each subsequent one is taller than the previous one). No matter how we cut the sheet, the \( 3n + 1 \) points marked in the figure will end up on the sides of different rectangles, so there cannot be fewer than \( 3n + 1 \).

## Answer

Problem