**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]**