Problem:
I have an 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 a sheet in one piece.) Let 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 and such that
for all .
Solution:
The upper bound requires an example of a set of blocks whose removal makes it impossible to remove any further blocks. It suffices to show that we can tile the plane by tiles containing one block for every five stamps so that no more blocks can be chosen. Two such tilings are shown below with one tile outlined in heavy lines. Given an section of the tiling take all blocks lying entirely within that section and add as many additional blocks as possible. If the basic tile is contained in an square, then the section is covered by tiles contained in a concentric square. Hence there are at most blocks entirely within the section. For an section of the tiling. there are at most blocks which lie partially in and partially out of that section (hence these block contain at most stamps in the square) and each of the additional blocks must contain one of these stamps. Thus there are at most additional blocks. Thus there are at most
blocks total.
The lower bound requires an argument. Suppose that we have a set of blocks whose removal makes removing any further blocks impossible.
- There are potential blocks of three consecutive stamps in a row or column. Each of these must meet at least one of the blocks removed. Conversely, each of the blocks removed meets at most 14 of these potential blocks
( 5 oriented the same way, including itself, and 9 oriented the orthogonal way). Therefore or
- Call a stamp used if it belongs to one of the removed blocks. Consider the five-stamp crosses centered at each stamp not on an edge of the sheet. Each cross must contain two used stamps. (One stamp not in the center is not enough to prevent another block from being torn out, and it is impossible to use one stamp in the center and use no other stamps in the cross.) In addition, each block not lying along an edge of the sheet lies entirely inside one cross. which thus contains three used stamps. There are at most of the blocks lying along the edges, hence there are at least crosses containing three used stamps.
Now count the number of pairs of a used stamp and a cross containing that stamp, in two ways. First counting block by block, we get used stamps. and each used stamp is contained in at most five crosses (exactly five if it is not on an edge), for a total of at most pairs. Next, counting cross by cross. each of the crosses contains at least two used stamps and we have at least crosses containing three used stamps, for a total of at leas pairs. Therefore
or
- Call a stamp used if it belongs to one of the removed blocks. Count the number of pairs consisting of a used stamp and an adjacent unused stamp. in two ways.
There are at least unused stamps which are not on an eige. Since no more blocks can be torn out, either the stamp to the left or right and einher the stamp above or below such an unused stamp must be used. Thus we have at least such pairs.
Each block removed is adjacent to at most eight other stamps. However these eight stamps contain two blocks of three consecutive stamps. Hence at most six of these eight stamps can be unused. Thus each of the block removed is involved in at most six pairs. Thus there are at most pairs.
Combining these we have
or
The problems on this page are the property of the MAA's American Mathematics Competitions