An equilateral triangle side n is divided into n2 equilateral triangles of side 1 by lines parallel to its sides, thus giving a network of nodes connected by line segments of length 1. What is the maximum number of segments that can be chosen so that no three chosen segments form a triangle?
Answer
n(n+1)
Solution
Every segment belongs to just one of the n(n+1)/2 triangles with base horizontal. We can choose at most 2 sides of each of these triangles, or n(n+1) in all. If we choose all the segments that are not horizontal, then we choose n(n+1) segments. Since every triangle has one horizontal segment, no three chosen segments form a triangle.
© John Scholes
jscholes@kalva.demon.co.uk
4 March 2004
Last corrected/updated 4 Mar 04