Let T(n) be a triangular portion of the triangular grid with n points on a side. It is an unsolved problem what the maximum number of points is that can be selected from T(n) so that no three selected points are the vertices of an equilateral triangle. For small values of n the maximum appears to be 2n-2. However, for T(12), shown below, I found more than 2*12-2=22 points, no three of which are the vertices of an equilateral triangle! How many can you find? Examples:

Here's an example of 5 points selected from T(4), no three of which are the vertices of an equilateral triangle. It turns out that this selection of 5 cannot be increased to 6 without three of the selected points being the vertices of an equilateral triangle. If we add the first point in the second row, we get Notice that three of the 6 s's are the vertices of an equilateral triangle.

There is a better selection of 6 points in T(4) no three of which are the vertices of an equilateral triangle.

I read the comment showing the general case for T(n) being at least 2n-2.  Looking at the pattern, it's pretty clear that no more points can be added.  However, I thought it was an incorrect conclusion to say that a configuration exceeding 22 would be completely different.  It might look completely different to a simple computer program, but not to us.

General case (2n-2):

   o
  s s
 s o s
s o o s

My variation:

      s
     s o
    s o o
   o s s s
  ? ? ? ? ?
 ? ? ? ? ? ?
? ? ? ? ? ? ?

So what new points can we put in the new area I designated with "?"s ?  Let's enlarge this triangle to size T(9) before investigating closer.
By investigation, and a little colorcoding on ms paint:

        s
       s o
      s o o
     s o o o
    s o o o o
   o s s s s s
  1 o o o o o 1
 2 1 o o o o 2 2
3 2 1 o o o 3 3 3

There are two triangle-shaped regions where points may be.  What we must avoid, though, is making triangles within each region, and making triangles that include points from both regions.  I "color-coded" the possible points with numbers to avoid the latter set of triangles.  If there are any points on 1s in the left triangle-shaped region, there cannot be any points on 1s on the right triangle-shaped region.  Similarly for 2s and 3s.

In this case, the triangle regions are small enough that we can find a maximum through brute force.  Here is a solution for T(9)!

        s
       s o
      s o o
     s o o o
    s o o o o
   o s s s s s        17 points
  s o o o o o o
 o s o o o o s s
o o s o o o s o s

The way I did it, I left two T(3) triangle shaped regions on the bottom.  But can I leave even bigger regions?  Yes, but there is a limit.  Aparently, in a T(n) triangle, this works only up to T(n/3) sized smaller regions, or the small regions become too close... though there might be some loopholes.

Solution for T(12)

           s
          s o
         s o o
        s o o o
       s o o o o
      s o o o o o
     s o o o o o o
    o s s s s s s s         24 points
   s o o o o o o o o
  o s o o o o o o s s
 o o s o o o o o s o s
o o o s o o o o s o o s

I would appreciate it if someone pointed out any errors I made.  I only checked these solutions by hand.

Posted by Tristan on 2005-08-19 07:55:22