HMMT 二月 2002 · 冲刺赛 · 第 2 题

(2) there exists a positive integer n such that the polyomino contains unit squares S , S , S , . . . , S such that S and S share an edge, S and T share an edge, and for all 1 2 3 n 1 n positive integers k < n , S and S share an edge. k k +1 We say a polyomino of a given rectangle spans the rectangle if for each of the four edges of the rectangle the polyomino contains a square whose edge lies on it. What is the minimum number of unit squares a polyomino can have if it spans a 128-by- 343 rectangle? 4 Solution: To span an a × b rectangle, we need at least a + b − 1 squares. Indeed, consider a square of the polyomino bordering the left edge of the rectangle and one bordering the right edge. There exists a path connecting these squares; suppose it runs through c different rows. Then the path requires at least b − 1 horizontal and c − 1 vertical steps, so it uses at least b + c − 1 different squares. However, since the polyomino also hits the top and bottom edges of the rectangle, it must run into the remaining a − c rows as well, so altogether we need at least a + b − 1 squares. On the other hand, this many squares suffice — just consider all the squares bordering the lower or right edges of the rectangle. So, in our case, the answer is 128 + 343 − 1 = 470 .