Problem

Source: ELMO Shortlist 2024/C4

Tags: Elmo, combinatorics



Let $n \geq 2$ be a positive integer. Let $\mathcal{R}$ be a connected set of unit squares on a grid. A bar is a rectangle of length or width $1$ which is fully contained in $\mathcal{R}$. A bar is special if it is not fully contained within any larger bar. Given that $\mathcal{R}$ contains special bars of sizes $1 \times 2,1 \times 3,\ldots,1 \times n$, find the smallest possible number of unit squares in $\mathcal{R}$. Srinivas Arun