Maths Olympiad Prep

Library / /911 of 1394

, 2025

Geometry Difficulty 5.4 AIME, harder Prove it United States

Problem:
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 180180, and area 20242024.

Solution

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×hw \times h.

Claim 1. w+h90w + h \leq 90.

Proof. The polyomino has at least 2w2w horizontal edges and at least 2h2h vertical edges. Moreover, it has a perimeter of 180180. Therefore, 2w+2h1802w + 2h \leq 180, so w+h90w + h \leq 90. \square

Claim 2. The dimensions of the bounding box are either 44×4644 \times 46, 45×4545 \times 45, or 46×4446 \times 44.

Proof. Note that hw2024hw \geq 2024 since it contains the polyomino with area 20242024. Suppose for sake of contradiction that h+w89h + w \leq 89. Then,
(hw)2=(h+w)24hw89242024=175, (h - w)^2 = (h + w)^2 - 4hw \leq 89^2 - 4 \cdot 2024 = -175,
contradiction. Therefore, h+w=90h + w = 90, so we can let (h,w)=(45+x,45x)(h,w) = (45 + x,45 - x). Then, 2025x2=hw20242025 - x^2 = hw \geq 2024 implies that x{1,0,1}x \in \{-1,0,1\}, as desired. \square

In the first and third cases, the bounding box has area 20242024, so it must be the entire polyomino, giving us the 44×4644 \times 46 rectangle (and its rotation) as a possible answer. In the second case, the bounding box has area 20252025, so one cell must be removed to form the polyomino. Removing the corner cell yields a polyomino with perimeter 180180, and removing any other cells yields a polyomino with perimeter greater than 180180. Therefore, the only other possibility is a 45×4545 \times 45 square missing a corner. Thus the answer is 2\boxed{2}.

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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.