Problems (with Solutions)
1 A set of identical square tiles with side length 1 is placed on a (very large) floor. Every tile after the first shares an entire edge with at least one tile that has already been placed.
- What is the largest possible perimeter for a figure made of 10 tiles?
- What is the smallest possible perimeter for a figure made of 10 tiles?
- What is the largest possible perimeter for a figure made of 2011 tiles?
- What is the smallest possible perimeter for a figure made of 2011 tiles?
Prove that your answers are correct.
Solution: The initial single tile has perimeter 4. Each time a tile is added, at most three edges are added and at least one edge of the previous boundary is eliminated, so the perimeter increases by at most 2 . Thus for $n$ tiles the maximum possible perimeter is $2(n+1)$ and this can be achieved (among other ways) by placing all of the tiles in a straight line. Therefore, the maximum perimeter for 10 tiles is 22 and for 2011 tiles, 4024.
The perimeter of a pattern is always greater than or equal to the perimeter of the smallest rectangle that encloses that pattern. To see this, project each side of the enclosing rectangle toward the pattern and every unit length of the rectangle will land on a different edge of the pattern. Any extra edges of the pattern, including concave "dents" and internal edges that surround holes, will only add to the pattern's perimeter.
Let $s$ and $t$ be the side lengths of a rectangle enclosing the pattern. Then, since the pattern fits inside the rectangle, $s t \geq n$. Also, from the previous paragraph, the perimeter $p \geq 2(s+t)$, so we have
$$
\begin{aligned}
p^{2} & \geq 4(s+t)^{2} \\
& \geq 4\left((s+t)^{2}-(s-t)^{2}\right) \quad \text { since }(s-t)^{2} \text { is not negative } \\
& =4(4 s t) \\
& \geq 16 n
\end{aligned}
$$

The inequality $p \geq 4 \sqrt{n}$ follows by taking the square root of both sides.
Since each tile has an even number of sides and sides are shared in pairs, the perimeter must be an even number.
For $n=10,4 \sqrt{10}>12$, so the perimeter is at least 14 . The number 14 can be achieved, for example, by placing the 10 tiles in a $2 \times 5$ rectangle, or in several patterns that fit inside a $3 \times 4$ rectangle.
For $n=2011,4 \sqrt{2011}>178$, so the perimeter is at least 180 . The number 180 can be achieved, for example, by filling a $45 \times 45$ rectangle and chopping off a line of $2025-2011=14$ tiles along an edge, beginning at a corner. (Several non-square starting rectangles will also work.)
To generalize this result, the minimal perimeter can always be obtained by fitting the pattern inside the smallest possible $n \times n$ or $n \times n-1$ rectangle, and sometimes in other ways as well.