Question 15
As shown in the diagram, Leon has a $ 5\times5 $ sheet of stamps. He cuts out the
5 stamps marked X. In doing so, he satisfies the following three conditions.
(1) No stamps on the edge or at a corner can be cut.
(2) If two stamps share a common edge, they cannot both be cut.
(3) After cutting, the remaining part of the sheet is still in one connected piece.
As it turns out, 5 is the maximum number of stamps that can be cut. Now Leon has a $ 7 \times 7 $ sheet of stamps. What is the maximum number of stamps that can be cut if the same three conditions must be satisfied? Give a method for cutting that many stamps, and a proof that no larger number of stamps can be cut.
| | | | | |
| --- | --- | --- | --- | --- |
| | X | | X | |
| | | X | | |
| | X | | X | |
| | | | | |
5 stamps marked X. In doing so, he satisfies the following three conditions.
(1) No stamps on the edge or at a corner can be cut.
(2) If two stamps share a common edge, they cannot both be cut.
(3) After cutting, the remaining part of the sheet is still in one connected piece.
As it turns out, 5 is the maximum number of stamps that can be cut. Now Leon has a $ 7 \times 7 $ sheet of stamps. What is the maximum number of stamps that can be cut if the same three conditions must be satisfied? Give a method for cutting that many stamps, and a proof that no larger number of stamps can be cut.
| | | | | |
| --- | --- | --- | --- | --- |
| | X | | X | |
| | | X | | |
| | X | | X | |
| | | | | |