A319158 - OEIS

%I #24 Aug 14 2020 06:22:48

%S 0,1,2,4,6,9,13,18,23,29,35,43,51

%N Given an equilateral triangular grid with side n, containing n(n+1)/2 points, a(n) is the minimal number of points to be selected, such that any equilateral triangle of points will include at least one of the selection, if the triangle has the same orientation as the grid.

%C This is the complementary problem to A157795: A157795(n) + a(n) = n(n+1)/2.

%C This is the same problem as A227116, except that here the triangles must have the same orientation as the grid.  Here, the triangle's sides must be aligned with the sides of the grid, and the horizontal side of the triangle must be its base (assuming the grid has a horizontal base).  A227116 is different in that it also includes upside-down triangles, rotated 180 degrees compared to the grid, since these have sides aligned with the grid (but different orientation).

%H Ed Wynn, <a href="https://arxiv.org/abs/1810.12975">A comparison of encodings for cardinality constraints in a SAT solver</a>, arXiv:1810.12975 [cs.LO], 2018.

%e For n=5, there is a unique solution for a(5)=6 (representing selected points by O):

%e         O

%e        . .

%e       , O ,

%e      . O O .

%e     O . , . O

%e It can be seen that this is not a valid solution for A227116 because of the upside-down triangle of commas.  One solution for A227116(5)=7 would be to select one of the commas as well.

%Y Cf. A157795, A227116, A319159.

%K nonn,more,hard

%O 1,3

%A _Ed Wynn_, Sep 12 2018