Competition problem — Combinatorics

Library / /93 of 94

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Divide an $m$ -by- $n$ rectangle into $mn$ nonoverlapping $1$ -by- $1$ squares. A polyomino of this rectangle is a subset of these unit squares such that for any two unit squares $S, T$ in the polyomino, either

(1) $S$ and $T$ share an edge or

(2) there exists a positive integer $n$ such that the polyomino contains unit squares $S_{1}, S_{2}, S_{3}, \ldots, S_{n}$ such that $S$ and $S_{1}$ share an edge, $S_{n}$ and $T$ share an edge, and for all positive integers $k < n$ , $S_{k}$ and $S_{k+1}$ share an edge.

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?

Solution

Solution:

To span an $a \times 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$ .

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.