MathDB

6

Part of 2002 USAMO

Problems(1)

USAMO 2002 Problem 6

Source:

9/30/2005
I have an n×nn \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)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 cc and dd such that 17n2−cn≤b(n)≤15n2+dn \dfrac{1}{7} n^2 - cn \leq b(n) \leq \dfrac{1}{5} n^2 + dn for all n>0n > 0.
USAMOcombinatoricscountinggrid