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 npositive 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 edgesof 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?
Solution: To span an a × b rectangle, we need at least a + b − 1 squares. Indeed, consider 4
a square of the polyomino bordering the left edge of the rectangle and one bordering theright edge. There exists a path connecting these squares; suppose it runs through c differentrows. Then the path requires at least b − 1 horizontal and c − 1 vertical steps, so it uses atleast b + c − 1 different squares. However, since the polyomino also hits the top and bottomedges of the rectangle, it must run into the remaining a − c rows as well, so altogether weneed at least a + b − 1 squares. On the other hand, this many squares suffice — just considerall the squares bordering the lower or right edges of the rectangle. So, in our case, the answeris 128 + 343 − 1 = 470 .