HMMT 二月 2025 · 团队赛 · 第 2 题
HMMT February 2025 — Team Round — Problem 2
题目详情
- [25] A polyomino is a connected figure constructed by joining one or more unit squares edge-to-edge. Determine, with proof, the number of non-congruent polyominoes with no holes, perimeter 180, and area 2024.
解析
- [25] A polyomino is a connected figure constructed by joining one or more unit squares edge-to-edge. Determine, with proof, the number of non-congruent polyominoes with no holes, perimeter 180, and area 2024. Proposed by: Albert Wang Answer: 2 Solution: Define the bounding box of a polyomino to be the smallest axis-aligned rectangle that contains the entire polyomino. Suppose a polyomino satisfying the given conditions has a bounding box with dimensions w × h . Claim 1. w + h ≤ 90. Proof. The polyomino has at least 2 w horizontal edges and at least 2 h vertical edges. Moreover, it has a perimeter of 180. Therefore, 2 w + 2 h ≤ 180, so w + h ≤ 90. Claim 2. The dimensions of the bounding box are either 44 × 46, 45 × 45, or 46 × 44. Proof. Note that hw ≥ 2024 since it contains the polyomino with area 2024. Suppose for sake of contradiction that h + w ≤ 89. Then, 2 2 2 ( h − w ) = ( h + w ) − 4 hw ≤ 89 − 4 · 2024 = − 175 , 2 contradiction. Therefore, h + w = 90, so we can let ( h, w ) = (45 + x, 45 − x ). Then, 2025 − x = hw ≥ 2024 implies that x ∈ {− 1 , 0 , 1 } , as desired. In the first and third cases, the bounding box has area 2024, so it must be the entire polyomino, giving us the 44 × 46 rectangle (and its rotation) as a possible answer. In the second case, the bounding box has area 2025, so one cell must be removed to form the polyomino. Removing the corner cell yields a polyomino with perimeter 180, and removing any other cells yields a polyomino with perimeter greater than 180. Therefore, the only other possibility is a 45 × 45 square missing a corner. Thus the answer is 2 .