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.
(In reply to
re(3): till now, 26 by owl)
Thanks for the rating, owl! I wasn't going to submit this problem because I have no complete solution for it, but a perplexus user asked me to submit it anyway.
I have a scheme for selecting points from T(n) not containing all the vertices of an equilateral triangle, but it doesn't beat your computer solution for T(12). So, between us, 24 is the current tentative maximum. (I checked your count of equilateral triangles using my previous problem "Cool Count". You are right; 1001=(12+2)(12+1)(12)(11)/4!)
By the way, I was wrong about josh's solution being the only one for n<12. My scheme produces a nonisomorphic solution for n=9.
|
|
Posted by McWorter
on 2005-08-19 03:30:26 |
re(4): till now, 26
