Problem: I have an $n \times n$ sheet of stamps, from which I've been asked
to tear out blocks of three adjacent stamps in a single row or column.
(I can only tear along the perforations separating adjacent stamps,
and each block must come out of the sheet in one piece.)
Let $b(n)$ be the smallest number of blocks I can tear out
and make it impossible to tear out any more blocks.
Prove that there are real constants $c$ and $d$ such that
\[ \frac{1}{7} n^2 - cn \leq b(n) \leq \frac{1}{5} n^2 + dn  \]
for all $n > 0$.

\end{enumerate}

Solution: For the lower bound: there are $2n(n-2)$ places one could put a block.
Note that each block eliminates at most $14$ such places.

For the upper bound, the construction of $\frac15$ is easy to build.
Here is an illustration of one possible construction
for $n=9$ which generalizes readily,
using only vertical blocks.
\[
\begin{bmatrix}
  A &   & E &   & I & L &   & P &   \\
  A &   & E & G &   & L &   & P & R \\
  A & C &   & G &   & L & N &   & R \\
    & C &   & G & J &   & N &   & R \\
    & C & F &   & J &   & N & Q &   \\
  B &   & F &   & J & M &   & Q &   \\
  B &   & F & H &   & M &   & Q & S \\
  B & D &   & H &   & M & O &   & S \\
    & D &   & H & K &   & O &   & S \\
\end{bmatrix}
\]

Actually, for the lower bound,
one may improve $1/7$ to $1/6$.
Count the number $A$ of pairs of adjacent squares
one of which is torn out and the other which is not:
\begin{itemize}
  \ii For every deleted block, there are eight neighboring squares,
  at least two on each long edge which have been deleted too.
  Hence $N \le 6b(n)$.
  \ii For every block still alive and not on the border, there are
  four neighboring squares, and clearly at least two are deleted.
  Hence $N \ge 2\left( (n-2)^2 - 3b(n) \right)$.
\end{itemize}
Collating these solves the problem.