For the upper bound, suppose first that $n=5k$. Now break the sheet up into rows and tile each row with $1 \times 5$ rectangles. In the odd rows, place a $1 \times 3$ piece covering the 3 leftmost squares of each $1 \times 5$ rectangle. In the even rows, place a $1 \times 3$ piece covering the 3 rightmost squares of each $1 \times 5$ rectangle. It is obvious that no more $1 \times 3$ pieces can be placed in the resulting board, and we have used $5k^2$ pieces in total, that is, a fifth of $25k^2=n^2$. If $n$ is not a multiple of $5$, let $n=5k+r$ with $0 \leq r \leq 4$ and apply the previous strategy in the bottom left $5k \times 5k$ part of the board. Cover the rest of the board with as many $1 \times 3$ pieces as you want. It's easy to see that the rest of the board has $(5k+r)^2-(5k)^2=(10k+r)r$ squares, and in any case, if after that we have problems with the boundaries of the $5k \times 5k$ part of the board, it would take at most $10k-1$ (the number of squares on the boundary, this is a very rough bound) to correct them. Besides, since $r \leq 4$, we would be using at most $5k^2+40k+16+10k-1$ pieces, that is, $5k^2+50k+15 \leq 5k^2+65k=n^2/5+13n$, so $b(n) \leq n^2/5+13n$. For the lower bound, suppose we've covered the board so that no more $1 \times 3$ pieces can be placed with $n^2/7-cn$ pieces. Place the $n \times n$ board on an infinite board and tile the infinite board with $1 \times 3$ rectangles in the obvious way, either horizontally or vertically. Choose the more popular orientation (if in the covering of the $n \times n$ board there are more horizontal pieces, tile with horizontal $1 \times 3$ rectangles, otherwise tile vertically). Suppose WLOG that the covering has more horizontal pieces and we've tiled with horizontal rectangles. Then there are at least $n^2/14-cn/2$ horizontal pieces and at most $n^2/14-cn/2$ vertical pieces. Now, if we number the columns $\pmod 3$, there will be a number $x$ in ${0, 1, 2}$ for which the number of horizontal pieces with their leftmost square in a column $\equiv x \pmod 3$ is maximal. Move the tiling of the infinite board so that the leftmost squares of the $1 \times 3$ rectangles are $\equiv x \pmod 3$. Now, the idea is that each $1 \times 3$ rectangle contained in the $n \times n$ board must have at least one covered square, but the vertical pieces kill at most $3$ rectangles each, the horizontal pieces $\equiv x$ kill at most $1$ and the other horizontal pieces kill at most $2$. By our choice of the tiling, at least one third of the horizontal pieces is $\equiv x$, and the number of killed rectangles is at most \[ [\dfrac{1}{2} \times \dfrac{1}{3}+2 \times \dfrac{1}{2} \times \dfrac{2}{3}+3 \times \dfrac{1}{2}](\dfrac{n^2}{7}-cn)=\dfrac{7}{3}(\dfrac{n^2}{7}-cn)=\dfrac{n^2}{3}-\dfrac{7cn}{3}. \] Now the number of $1 \times 3$ rectangles contained in the $n \times n$ board is $\dfrac{n^2}{3}$ minus some number that is bounded by $en$ for some large enough constant $e$ (as the number of rectangles lost at the boundaries is no more than $4n$), so setting a large enough $c$ will make it impossible for all rectangles to be killed, and this finishes the problem.

Simpler proof for the lower bound: Each block I tear out can prevent at most 14 other blocks from being torn out (5 parallel to it and 9 perpendicular to it). There are $ 2n(n-2) = 2n^2 - 4n$ total blocks on the board. Since we need make it so that we cannot tear out anymore blocks, we must have $ 14 b(n) \ge 2n^2 - 4n$ or $ \frac{n^2}{7} - \frac{2n}{7} \le b(n)$.

If I'm not mistaken, we can strengthen the lower bound... Let $R$ be the $n\times n$ sheet of stamps. Call a square or block good if it has been torn out and bad otherwise, and suppose we've torn out $b(n)$ blocks so that no bad blocks remain. Let $X$ be the number of pairs of neighboring squares with one good and one bad. First consider a good block $B$ (note that a good square must be part of a good block), which is surrounded by eight squares. Since there are two blocks next to $B$, and there are no bad blocks in $R$, we must have a good square in both. Thus $X\le(8-2)b(n)=6b(n)$. Now consider a bad square $S$, which is surrounded by four squares. If three or more of these four squares are bad, then we have a bad block, so at most two of them are bad. Hence if $S$ is not on the border of $R$, then it must border at least two good squares. But there are at least $(n-2)^2-3b(n)$ bad squares not on the border of $R$, so $X\ge2(n-2)^2-6b(n)$. Finally, we have \[6b(n)\ge X\ge2(n-2)^2-6b(n)\implies b(n)\ge\frac{1}{6}(n-2)^2,\]which is clearly sufficient.

Lower bound: Let $h$ and $c$ be the total number of horizontal and vertical blocks, respectively. Let $h_i$ and $c_i$ be the number of horizontal blocks and vertical blocks torn out in row $i$. Note that every horizontal block torn out prevents us from tearing out at most $5$ other horizontal blocks in row $i$, and each vertical block torn out prevents us from tearing out at most $3$ other vertical blocks in row $i$. Thus, $5h_i + 3c_i \ge n - 2$. Since each vertical block torn out is in $3$ rows, summing over all rows, each vertical block is counted 3 times and each horizontal block counted once, so \[ \sum_{i = 1}^{n} (5h_i + 3c_i) = 5h + 9c \ge n(n - 2)\] By using the same method for columns, we also get $9h + 5c \ge n(n - 2)$. Adding the two equations gives us \[14h + 14c = 14b(n) \ge 2n^2 - 4n \implies b(n) \ge \dfrac {n^2 - 2n} {7}\]

One bad way to approach the lower bound is to observe that, in any $3 \times 7$ rectangle on the grid, at least $9$ of these squares must be covered by $1 \times 3$ blocks (this can be done with casework). $\frac{9}{21} = \frac{3}{7}$, and the result follows via a contradiction argument.

Does this work for the lower bound? Let $x$ be equal to the number of squares covered by a $1 \times3$ block For any square S, consider the 4 squares adjacent to it. If S is empty, at least 2 of these squares must be covered. If S is covered, and the center piece of a block, at least 2 of these must be covered. If S is covered, and the edge piece of a block, at least one of these must be covered. Thus (up to some linear error term because of the perimeter blocks) $$ x \ge \frac{2\cdot open + 2\cdot center + edge}{4} $$Since $\frac{1}{3}$ of all covered squares are center squares, we have $$ 4x \ge 2(n^2 - x) + \frac{2x}{3} + \frac{2x}{3}$$which rearranges to $x \ge \frac{3}{7}n^2$ as desired

gubsheep wrote: One bad way to approach the lower bound is to observe that, in any $3 \times 7$ rectangle on the grid, at least $9$ of these squares must be covered by $1 \times 3$ blocks (this can be done with casework). $\frac{9}{21} = \frac{3}{7}$, and the result follows via a contradiction argument. Why are you saying it's the "bad way" ? It's what I did, and it seems pretty straightforward despite the few caseworks...

Am I allowed to tear out the square which is not on the boundary? (In other words, am I allowed to make holes?)

MarkBcc168 wrote: Am I allowed to tear out the square which is not on the boundary? (In other words, am I allowed to make holes?) Yes. You can tear out the squares in any order.

If whatever written below is correct the lower bound can be strengthened to $\frac{4}{23}n^2$ from $\frac{1}{6}n^2$...

continued from the above...

Let a tromino denote a block of $3$ stamps which satisfy the condition in the problem. Call a tiling of an $n \times n$ grid full if no more trominos can be added to the tiling. We first prove the upper bound. Note that there is a full tiling of a $5 \times 5$ grid with exactly $5$ trominos: indeed, in the first, third, and fifth rows, add a tromino that covers the first three squares of the row, and in the second and fourth rows, add a tromino which covers the last three squares. This is clearly a full tiling (since the maximal size of a contiguous group of untouched squares in the grid is $2$). Now, let $n = 5k + r$, where $k, r$ are integers are $r < 5$. Partition the top-left $5k \times 5k$ grid of the $n \times n$ grid into non-overlapping $5 \times 5$ grids. In each such grid, repeat the above described tiling for the $5 \times 5$ grid. It is clear that this tiling of the top-left $5k \times 5k$ grid is full. Now, there are $r$ rows and $r$ columns which have so far been untouched; in each such row or column, we can clearly use at most $\frac{n}{3}$ trominos. Hence, these $2r$ rows and columns will contribute at most $\frac{2nr}{3} \leq \frac{2 \cdot 4}{3}n = \frac{8}{3}n$ trominos, so we may take $d = \frac{8}{3}$. This proves the upper bound. Now, we prove the lower bound. Consider a graph on the set of all possible trominos of the $n \times n$ grid. Connect two trominos with an edge if they intersect. Note that there are $2n(n - 2)$ vertices in this graph. The maximal degree of a vertex in this graph is $13$: for any given tromino, there are at most $9$ trominos intersecting it which are perpendicular to it, and $4$ trominos intersecting it which are parallel to it. Now, consider a full tiling of the $n \times n$ grid. This corresponds to a maximal independent set of the graph. Suppose there are $j$ vertices in this independent set. Every vertex of the graph must be either adjacent to this set or in the set. However, the maximum number of vertices adjacent to this set is $13j$. Hence, we have \begin{align*} 13j + j&\geq 2n(n - 2) \\ j &\geq \frac{1}{7}n^2 - \frac{2}{7}n \\ \end{align*}This implies that we can take $c = \frac{2}{7}$, completing the proof. $\Box$

Not so Quick sketch (very bashy lol): $b = \frac{2}{5}$ and $c = \frac{2}{7}.$ PROOF FOR UPPER BOUND: Bash out cases for $n = 1, 2, 3, 4, 5, 6, 7, 8, 9.$ $b(n) = 5$. This means $\frac{3}{5}$ of the tiles in a $5\times 5$ are teared out. This will be important We proceed with induction. Base case is done. For all the rest of $n = 2k + m$ for $k \ge 2$ and $0 \le m \le 4$, consider $n = 2(k-1) + m $. We can split this $2(k-1) + m$ into 4 "different" groups of rectangles. An $m \times m$ rectangle, $k-1$ total $m \times 5$ rectangles, $k-1$ total $5 \times m$ rectangles, and $(k-1)^2$ total $5 \times 5$ rectangles. We then add one $m \times 5$ rectangle, one $5 \times m$ rectangle, and $2k-1$ total $5\times 5$ rectangles. Because we assume it works for $2(k-1) + m$, we let each of the rectangles from each of the $4$ groups have the same "tiling". It is easily proven that this leaves room for no blocks to be teared out. Next, because everything except for the $m\times m$ rectangle has a dimension of $5$ in it, we can see that $\frac{3}{5}$ of the tiles in these rectangles are teared out, so if $A$ is the area of a specific rectangle, there are a total of $\frac{A}{5}$ blocks that are teared out. Therefore, not including the $m\times m$ square, there are a total of $\frac{n^2-m^2}{5}$. This is an integer because we defined m as the remainder of $n/5$. Finally, we just need to count how many blocks are teared out in the $m\times m$ rectangle. We could just let $d$ be arbitrarily large and $dn \ge T$ where $T$ is the total number of blocks teared out in the $m\times m$ rectangle, but $d = \frac{2}{5}$ is specific. There are a lot of proofs for the lower bound already.

Not even 20 mohs imo. Replace tearing out stamps with covering/tiling them. Consider a sheet with every possible block of stamps drawn out already (on top of each other). It is clear that there are $2n(n-2)$ of these. It is also not hard to verify that any block of stamps covers at most 14 blocks, including itself: 9 blocks with opposite orientation and 5 with similar orientation. If there are no more blocks to be covered, this means that every block of stamps is covered. In order for this to happen, we need at least $$\frac{1}{14}\cdot 2n(n-2)=\frac{1}{7}n-\frac{2}{7}n$$stamps, so $\tfrac{1}{7}n^2-cn \leq b(n)$. This establishes the upper bound. It remains to prove the upper bound. Note that we only care about the asymptotic behavior of $n$, since if $b(n)$ is large for some interval that doesn't extend infinitely in the positive direction, we can just make $d$ extremely large to account for this. By selecting an appropriate choice of $d$ such that $b(n)\leq \tfrac{1}{5}dn$ for $n \in \{1,2,\ldots,15\}$, it suffices to verify $n \geq 16$. Now let $f(n)$ denote the largest positive multiple of $5$ such that $n \equiv f(n) \pmod{3}$ and $n \geq f(n)$. Note that for $n \geq 16$ this function is well-defined, since $\{5,10,15\}$ covers all residues mod 3. Also observe that $n-f(n) \leq 15$. Define a "cool tiling" to be a tiling of a 5x5 sheet of stamps that looks as shown: [asy][asy] unitsize(35); for(int i=0; i<=5; ++i) { draw((0,i)--(5,i)); draw((i,0)--(i,5)); } fill((0.2,0.2)--(0.2,0.8)--(2.8,0.8)--(2.8,0.2)--cycle,red); fill((0.2,2.2)--(0.2,2.8)--(2.8,2.8)--(2.8,2.2)--cycle,red); fill((0.2,4.2)--(0.2,4.8)--(2.8,4.8)--(2.8,4.2)--cycle,red); fill((2.2,1.2)--(2.2,1.8)--(4.8,1.8)--(4.8,1.2)--cycle,red); fill((2.2,3.2)--(2.2,3.8)--(4.8,3.8)--(4.8,3.2)--cycle,red); [/asy][/asy] where red bars represent stamps torn out/blocks tiled. It is clear that by repeating this tiling and mirroring alternating rows (but not columns), we obtain a tiling that involves $5k^2$ blocks in a $5k \times 5k$ grid. Here is an example for $k=3$. [asy][asy] unitsize(12); for (int j=0; j<=10; j+=5) { for (int k=0;k<=10; k+=5) { for(int i=0; i<=5; ++i) { draw((j,i+k)--(5+j,i+k)); draw((j+i,k)--(j+i,5+k)); } if (k==5) { fill((j+0.2,k+1.2)--(j+0.2,k+1.8)--(j+2.8,k+1.8)--(j+2.8,k+1.2)--cycle,red); fill((j+0.2,k+3.2)--(j+0.2,k+3.8)--(j+2.8,k+3.8)--(j+2.8,k+3.2)--cycle,red); fill((j+2.2,k+0.2)--(j+2.2,k+0.8)--(j+4.8,k+0.8)--(j+4.8,k+0.2)--cycle,red); fill((j+2.2,k+2.2)--(j+2.2,k+2.8)--(j+4.8,k+2.8)--(j+4.8,k+2.2)--cycle,red); fill((j+2.2,k+4.2)--(j+2.2,k+4.8)--(j+4.8,k+4.8)--(j+4.8,k+4.2)--cycle,red); } else { fill((j+0.2,k+0.2)--(j+0.2,k+0.8)--(j+2.8,k+0.8)--(j+2.8,k+0.2)--cycle,red); fill((j+0.2,k+2.2)--(j+0.2,k+2.8)--(j+2.8,k+2.8)--(j+2.8,k+2.2)--cycle,red); fill((j+0.2,k+4.2)--(j+0.2,k+4.8)--(j+2.8,k+4.8)--(j+2.8,k+4.2)--cycle,red); fill((j+2.2,k+1.2)--(j+2.2,k+1.8)--(j+4.8,k+1.8)--(j+4.8,k+1.2)--cycle,red); fill((j+2.2,k+3.2)--(j+2.2,k+3.8)--(j+4.8,k+3.8)--(j+4.8,k+3.2)--cycle,red); } } } [/asy][/asy] Now for the general construction. For any $n \geq 16$, we can use the tiling shown above to tile the $f(n) \times f(n)$ square in the lower left. Then we can cover all of the remaining stamps. Here is an easily generalizable example for $n=16$: [asy][asy] unitsize(12); for (int i=0; i<=16;++i) { draw((0,i)--(16,i)); draw((i,0)--(i,16)); } draw((0,10)--(16,10),linewidth(2)); draw((10,0)--(10,10),linewidth(2)); for (int j=0; j<=5; j+=5) { for (int k=0;k<=5; k+=5) { if (k==5) { fill((j+0.2,k+1.2)--(j+0.2,k+1.8)--(j+2.8,k+1.8)--(j+2.8,k+1.2)--cycle,red); fill((j+0.2,k+3.2)--(j+0.2,k+3.8)--(j+2.8,k+3.8)--(j+2.8,k+3.2)--cycle,red); fill((j+2.2,k+0.2)--(j+2.2,k+0.8)--(j+4.8,k+0.8)--(j+4.8,k+0.2)--cycle,red); fill((j+2.2,k+2.2)--(j+2.2,k+2.8)--(j+4.8,k+2.8)--(j+4.8,k+2.2)--cycle,red); fill((j+2.2,k+4.2)--(j+2.2,k+4.8)--(j+4.8,k+4.8)--(j+4.8,k+4.2)--cycle,red); } else { fill((j+0.2,k+0.2)--(j+0.2,k+0.8)--(j+2.8,k+0.8)--(j+2.8,k+0.2)--cycle,red); fill((j+0.2,k+2.2)--(j+0.2,k+2.8)--(j+2.8,k+2.8)--(j+2.8,k+2.2)--cycle,red); fill((j+0.2,k+4.2)--(j+0.2,k+4.8)--(j+2.8,k+4.8)--(j+2.8,k+4.2)--cycle,red); fill((j+2.2,k+1.2)--(j+2.2,k+1.8)--(j+4.8,k+1.8)--(j+4.8,k+1.2)--cycle,red); fill((j+2.2,k+3.2)--(j+2.2,k+3.8)--(j+4.8,k+3.8)--(j+4.8,k+3.2)--cycle,red); } } } for (int i=0; i<10;++i) { fill((10.2,0.2+i)--(10.2,0.8+i)--(12.8,0.8+i)--(12.8,0.2+i)--cycle,red); fill((13.2,0.2+i)--(13.2,0.8+i)--(15.8,0.8+i)--(15.8,0.2+i)--cycle,red); } for (int i=0; i<16;++i) { fill((0.2+i,10.2)--(0.8+i,10.2)--(0.8+i,12.8)--(0.2+i,12.8)--cycle,red); fill((0.2+i,13.2)--(0.8+i,13.2)--(0.8+i,15.8)--(0.2+i,15.8)--cycle,red); } [/asy][/asy] It is clear that such a tiling uses: $$\frac{1}{5}f(n)^2+2f(n)(n-f(n))+(n-f(n))^2 \leq \frac{1}{5}n^2+30n+225.$$Picking a large enough $d$, we have $\tfrac{1}{5}n^2+dn\geq \tfrac{1}{5}n^2+30n+225$. Hence it is possible to tile the $n \times n$ grid with $\tfrac{1}{5}n^2+dn$ blocks, so $b(n) \leq \tfrac{1}{5}n^2+dn$. This establishes the upper bound. $\blacksquare$

Call a set of 3 in a rows of either orientation a tromino. $\textbf{Lower Bound: }$. Note that there are $2\cdot n \cdot (n-2)=2n^2-4n$ tromino. Then, note that each tear deals with at most $3\cdot 3$ verticals + $5$ horizontals, for a total of 14 trominos precluded by each tear. Thus, since all trominos are precluded, \[14\cdot b(n) \geq 2n^2-4n\]Or, \[b(n)\geq \frac{1}{7}n^2-\frac{2}{7}n\]$\blacksquare$. $\textbf{Upper Bound: }$. We provide a construction, in each of the odd columns, number the squares from $1\to n$, then for all $k\geq 0$, tear the triplets $(5k+3,5k+4,5k+5)$. In the even columns, for all $k\geq 0$, tear $(5k,5k+1,5k+2)$. Finally, note that depending on $n$, the bottom row may have that half of the columns are empty there, and if those columns have $\geq 3$ empty squares, make a tear there. Thus, the total number of trominos used here is at most \[b(n) \leq n\cdot\lceil \frac{n}{5}\rceil \leq \frac{1}{5}n^2+n\]$\blacksquare$.

For the upper bound, let $n = 5k+r$. For the $5k \times 5k$ grid, on each row, (identify a block by its center piece) tear the blocks $2 \pmod 5$ and $4 \pmod 5$ alternately, which works. This uses $\frac{1}{5} (5k)^2 = 5k^2$ blocks. For the remaining grid, cover everything with blocks, which uses at most $10kr + r^2 \le 40k + 16$ blocks (yes this is terrible bounding but no one cares about constants). So a total of at most $5k^2 + 40k + 16 = \frac{1}{5} n^2 + 8n$ blocks are used so we may pick $d = 8$. For the lower bound, define the weight of a block in a particular row/column to be $3$ if its in the opposite orientation of the row/column and $5$ otherwise, this denotes the number of squares the block ensures needn't be tiled by other new blocks. Clearly, every row/column must have weight at least $n-2$ so the total weight summed across the entire board must be at least $2n(n-2)$. But also, each block has a weight of at most $9$ perpendicular to it and $5$ parallel to it, which is at most $14$. So we have $14b(n) \ge 2n(n-2) \implies b(n) \ge \frac{1}{7}n^2 - \frac{2n}{7}$ so picking $c = \frac{2}{7}$ works. $\blacksquare$

Here is a proof of the lower bound only (for $c=\frac{2}{7}$). Suppose that we have cut out a maximal number of blocks. To each removed block assign the blocks intersecting it (including the removed block itself). It is easy to see that there are at most $14$ blocks assigned to each block. In addition, each block is assigned to at least one removed block. Hence $14b(n) \geq 2n(n-2)$ (this is the number of blocks), so we are done.

Note that there are a total of $n(n-2)$ possible ways to cut a horizontal block and as many to cut a vertical one. Each cut block renders at most $14$ other ones not possible to be cut out, so $14b(n)\ge 2n(n-2)$ which gives us our lower bound. $~$ Now, to prove the upper bound we simply need to find successful cases. First, let $5k$ be the smallest multiple of $5$ less than $n$. Now, cut the bottom-left $5k\times 5k$ into $5k$ vertical strips, and in the left-most vertical strip cut out the lowest possible block, then going up: skip two and cut the next three out, and so on. In the second left-most strip, do the same but skipping one at the beginning. In the third left-most strip, do the same but skipping two at the beginning. In the fourth left-most strip, do the same as the first left-most strip, and repeat this process every three. $~$ Now, we see that this gives us $b(5k)\le 5k^2$, which proves what we want about $n=5k$. Additionally, note that even if we cut blocks super suboptimally in the remaining top horizontal lines and right vertical lines, we will only ever cut out $O(n)$ strips, so we are done.