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?
o
o o
o o o
o o o o
o o o o o
o o o o o o
o o o o o o o
o o o o o o o o
o o o o o o o o o
o o o o o o o o o o
o o o o o o o o o o o
o o o o o o o o o o o o
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 don't have a solution (yet) with more than 23 points, though maybe one could be found using dynamic programming.
My thought is to try an algorithm to fill in the grid. The basic idea would be, at a given step, there are some points that are already chosen, some that are already forbidden, and some that haven't been accounted for yet. For each point not accounted for, if we were to choose it, it would make some others forbidden. If we optimize (using dynamic programming) according to the number of forbidden points, this should produce an optimal solution (I think).
I have neither the time nor the skill at dynamic programming to implement this, though...
BTW: what is this about drinking my blood!? i don't have a whole lot to spare...
dynamic programming anyone?
