A319158 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.

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

Offset

1,3

Comments

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

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).

Links

Table of n, a(n) for n=1..13.

Ed Wynn, A comparison of encodings for cardinality constraints in a SAT solver, arXiv:1810.12975 [cs.LO], 2018.

Example

For n=5, there is a unique solution for a(5)=6 (representing selected points by O):
        O
       . .
      , O ,
     . O O .
    O . , . O
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.

Crossrefs

Cf. A157795, A227116, A319159.

Sequence in context: A183920 A079717 A247179 * A175780 A114830 A177239

Adjacent sequences: A319155 A319156 A319157 * A319159 A319160 A319161

Keyword

nonn,more,hard

Author

Ed Wynn, Sep 12 2018

Status

approved