MathDB

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

\dfrac{1}{7} n^2 - cn \leq b(n) \leq \dfrac{1}{5} n^2 + dn

for all

n > 0

Problem Statement