|
| |
|
|
A227308
|
|
Given an equilateral triangular grid with side n consisting of n(n+1)/2 points, a(n) is the maximum number of points that can be painted so that, if any 3 of the painted ones are chosen, they do not form an equilateral triangle with sides parallel to the grid.
|
|
8
|
|
|
|
1, 2, 4, 6, 8, 12, 14, 18, 22, 26, 30, 34, 39, 44, 49
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Numbers found by an exhaustive computational search for all solutions. This sequence is complementary to A227116: A227116(n) + A227308(n) = n(n+1)/2.
Up to n=12 there is always a symmetric maximal solution. For n=13 and n=15 symmetric solutions contain at most a(n)-1 painted points. - Heinrich Ludwig, Oct 26 2013
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
n = 11. At most a(11) = 30 points (X) of 66 can be painted, while 36 (.) must remain unpainted.
.
X X
X . X
X . . X
X . . . X
X . . . . X
. X X . X X .
. X . X X . X .
. . X X . X X . .
X . . . . . . . . X
. X X X . . . X X X .
In this pattern there is no equilateral subtriangle with all vertices = X and sides parallel to the whole triangle.
|
|
|
MATHEMATICA
|
ivar[r_, c_] := r*(r-1)/2 + c; a[n_] := Block[{m, qq, nv = n*(n+1)/2, ne}, qq = Union[ Flatten[Table[{ivar[r, c], ivar[r-j, c], ivar[r, c+j]}, {r, 2, n}, {c, r - 1}, {j, Min[r - 1, r - c]}], 2], Flatten[Table[{ivar[r, c], ivar[r + j, c], ivar[r, c - j]}, {r, 2, n}, {c, 2, r}, {j, Min[c - 1, n - r]}], 2]]; ne = Length@qq; m = Table[0, {ne}, {nv}]; Do[m[[i, qq[[i]]]] = 1, {i, ne}]; Total@ Quiet@ LinearProgramming[ Table[-1, {nv}], m, Table[{2, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; Array[a, 9] (* Giovanni Resta, Sep 19 2013 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,hard,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
