|
%I #31 Jul 07 2023 14:56:07
%S 1,2,4,6,8,12,14,18,22,26,30,34,39,44,49
%N 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.
%C Numbers found by an exhaustive computational search for all solutions. This sequence is complementary to A227116: A227116(n) + A227308(n) = n(n+1)/2.
%C 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
%H Heinrich Ludwig, <a href="/A227308/a227308_1.png">Illustration of a(2)..a(15)</a>
%H Giovanni Resta, <a href="/A227308/a227308.png">Illustration of a(3)-a(14)</a>
%e n = 11. At most a(11) = 30 points (X) of 66 can be painted, while 36 (.) must remain unpainted.
%e .
%e X X
%e X . X
%e X . . X
%e X . . . X
%e X . . . . X
%e . X X . X X .
%e . X . X X . X .
%e . . X X . X X . .
%e X . . . . . . . . X
%e . X X X . . . X X X .
%e In this pattern there is no equilateral subtriangle with all vertices = X and sides parallel to the whole triangle.
%t 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 *)
%Y Cf. A227116 (the complementary problem), A152125, A227133, A002717.
%K nonn,hard,more
%O 1,2
%A _Heinrich Ludwig_, Jul 06 2013
%E a(12), a(13) from _Heinrich Ludwig_, Sep 02 2013
%E a(14) from _Giovanni Resta_, Sep 19 2013
%E a(15) from _Heinrich Ludwig_, Oct 26 2013
|
