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 $9\times9$ 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.
(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 $9\times9$ 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.