2002 USAMO 第 6 题

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$.

我有一张 $n \times n$ 张邮票，我被要求从其中撕下单行或单列中的三块相邻的邮票。 (我只能沿着分隔相邻邮票的穿孔撕开，并且每个块必须从纸张中整块出来。)令 $b(n)$ 为我可以撕下的最小块数，并且无法撕下更多块。证明存在实常量 $c$ 和 $d$ 使得

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

对于所有 $n > 0$。