The following is a problem from USAMO 2002:
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$.
The solution is given here
https://artofproblemsolving.com/wiki/index.php?title=2002_USAMO_Problems/Problem_6
I, however couldn't understand the second statement of the solution itself.He says that
" It suffices to show that we can tile the plane by tiles containing one block for every five stamps such that no more blocks can be chosen."
Why is he trying to show that one block for every 5 stamps? Isn't it three stamps I am supposed to remove? He has shown an example in the tiling he gave, however I am surprised as to how and why will it help me? Any help please
My Try: I first take a 3 x 3 tile and try to tear it. I can tear it along either of the three rows or three columns giving me b(n) = 3. Now when I apply the inequality, I get
$\dfrac{9}{7} - 3c \leq 3 \leq \dfrac{9}{5} + 3d$
I do the same for n = 4 and try to observe but not able to get anything.
A very small doubt: I am quite weak with the concept of infinity. I think infinity is a real number, yeah I have seen some people recommending me not to mess with infinity when I am talking about numbers, however is it not possible for me to assign c and d infinity or sometimes I feel for an arbitrarily large n, may be infinity would also fail. Any comments on this thinking of mine?
Thanks in advance
Let's first try to read the first sentence of the solution:
Note that $b(n)$ is the smallest number of blocks you can tear out. This follows that for any way to tear out the blocks of stamps from the $n\times n$ sheet to get $K$ blocks then you always have $b(n) \le K$. Therefore, if you can construct a way to give $\frac 15 n^2+dn$ blocks for some constant $d$ that holds for any $n$ then $b(n) \le \frac{1}{5}n^2+dn$ for any $n$.
Hence, to construct such way to tear out the sheet, the author tried to tile the sheet with $1\times 5$ blocks and choose $1 \times 3$ blocks within such $1\times 5$ blocks such that the remaining $2$ stamps don't form $1 \times 3$ block with other stamps. Of course, you can also start by tiling $1 \times 3$ block but since you want minimal number of blocks then you would need $2$ stamps in between two horizontal $1 \times 3$ blocks (there's no point putting more than $2$ stamps in between because it would otherwise create another $1 \times 3$ block; if there is one stamp in between then you would probably get more $1 \times 3$ blocks comparing to the $2$ stamps). It's essentially the same as tiling with $1 \times 5$ blocks.
Note that if you find $c,d$ that works then any $C,D$ larger than these two will also work. This is because $\frac 17 n^2-Cn < \frac 17 n^2-cn$ and $\frac 15 n^2+dn< \frac 15 n^2+Dn.$ Hence, there is no point taking $c,d$ to be infinity for this problem because that would make the problem to be too trivial (you don't even need the conditions given in the problem). Plus, the problem asks $c,d$ to be real constants, i.e. some specific numbers.