Inventory017:  A problem in the triangular grid (proposed by Stephen C. Locke, 12/12/01).

Frederic Havet posed the following problem, which arises from the question of assigning radio frequencies for mobile telephones to points on a triangular grid.

A unit triangle is an equilateral triangle with all sides of length one. Let T denote the (infinite) triangular plane grid (lattice, tessellation) of unit triangles. A subset W of the vertices of T is called triangle-free if W contains the vertex set of no unit triangle.
Let S be a finite triangle-free subset of the vertices of T, and let n=|S|. Prove that S contains a set K of cardinality at least 4n/9 and with the property that no two vertices of K are at distance one.

Discussion. [SCL, 12/12/01]:  I can do something better than 2n/5. The upper bound of 4n/9 is easy to see. Take a unit triangle X and let Y denote the set of vertices of T, each at which is distance one from at least one vertex of X.

Bibliography.

Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]