Problem:
An animal with cells is a connected figure consisting of equal-sized square cells. The figure below shows an -cell animal.
A dinosaur is an animal with at least cells. It is said to be primitive if its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.
Animals are also called polyominoes. They can be defined inductively. Two cells are adjacent if they share a complete edge. A single cell is an animal, and given an animal with -cells, one with cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.
Solution:
Let denote the minimum number of cells in a dinosaur; the number this year is .
Claim: The maximum number of cells in a primitive dinosaur is .
First, a primitive dinosaur can contain up to cells. To see this, consider a dinosaur in the form of a cross consisting of a central cell and four arms with cells apiece. No connected figure with at least cells can be removed without disconnecting the dinosaur.
The proof that no dinosaur with at least cells is primitive relies on the following result.
Lemma. Let be a dinosaur having at least cells, and let (red) and (black) be two complementary animals in , i.e., and . Suppose . Then can be augmented to produce animals and such that at least one of the following holds:
(i) and ,
(ii) ,
(iii) .
Proof. If there is a black cell adjacent to that can be made red without disconnecting , then (ii) holds. Otherwise, there is a black cell adjacent to whose removal disconnects . Of the squares adjacent to , at least one is red, and at least one is black, otherwise would be disconnected. Then there are at most three resulting components of after the removal of . Without loss of generality, is the largest of the remaining components. (Note that or may be empty.) Now has at least cells. Let . Then . If , then and (i) holds. If then either (ii) or (iii) holds, depending on whether or not.
Starting with , repeatedly apply the Lemma. Because in alternatives (ii) and (iii) increases but remains less than , alternative (i) eventually must occur. This shows that no dinosaur with at least cells is primitive.
This problem was suggested by Reid Barton.
The problems on this page are the property of the MAA's American Mathematics Competitions