MathDB
primitive polyominoes

Source: USAMO 2007

April 26, 2007
searchinequalitiesinductiongraph theorycombinatorics proposedcombinatorics

Problem Statement

An animal with nn cells is a connected figure consisting of nn equal-sized cells[1].
A dinosaur is an animal with at least 20072007 cells. It is said to be primitive it its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.
(1) 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 nn cells, one with n+1n+1 cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.