A319159 - OEIS

%I #23 Aug 08 2020 11:11:12

%S 1,2,4,7,11,16,22,28,35,44,53,63,74,86

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

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

%C This is the same problem as A227116 and A319158, except that here the triangles may have any orientation.  Due to the additional requirements, a(n) >= A227116(n) >= A319158(n).

%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=4, this sequence has the same value a(4)=4 as A227116 and A319158, but if we look at the three solutions to those sequences (unique up to symmetry), representing selected points by O:

%e         O             O             O

%e        O ,           . ,           . .

%e       , . O         , O .         . O .

%e      . O , .       O . , O       . O O .

%e We see that only the last of these is a solution here -- the others have rotated triangles not including any selected point (for example, as shown with commas).  The last selection is therefore the unique solution (up to symmetry) for a(4)=4.

%Y Cf. A227116, A240114, A319158.

%K nonn,more,hard

%O 1,2

%A _Ed Wynn_, Sep 12 2018