A350685 Maximum number of points on a hexagonal grid of side length n without arithmetic progression, i.e., no point is exactly at the center between two other points.

0, 1, 6, 12, 18, 27, 33, 42

Offset

0,3

Comments

The hexagonal grid of size n, or side length n, consists of 2n-1 centered rows of respective length (number of cells or available grid points) n, n+1, ..., 2n-1, 2n-2, ..., n, for a total of A003215(n-1) = 3n(n-1) + 1 cells, cf. examples.

The forbidden arithmetic progressions can also be stated by requiring that all 3-element subsets must be non-averaging, i.e., none of the three points can be the center or midpoint of the two other points.

Lower bounds for the next terms are a(8) >= 52, a(9) >= 59, a(10) >= 68, a(11) >= 80. - M. A. Achterberg, Feb 10 2022

Links

Table of n, a(n) for n=0..7.

Al Zimmermann, Programming Contest: AP Math, Sep. - Dec. 2021

Example

For n = 2, the best solution is to leave out only the central point, which yields a(2) = 6, see the drawing below. If the central point is used, for any of the peripheral points, the opposite one must remain empty, so the maximum score is only 1 + 3 = 4.
n = 0:     n = 1:     n = 2:      n = 3:   X X O     n = 4:  X O X X
                            X X           X X O X           X X O X X
      []         X         X O X         O O O X X         O X O O O O
                            X X           X X O X         X O O O O O X
                                           X X O           O O O O X O
n = 5:    X X O X X                                         X X O X X
         X X O O X X                                         X X O X
        O O O O O O O
       X O X O O X O X
      X X O O O O O X X
       X O O O O O O X
        O O O X O O O
         X X O O X X
          X X O X X

Crossrefs

Cf. A003215 (hex numbers 3n(n-1)+1).

Sequence in context: A246295 A108587 A079424 * A270383 A088345 A057826

Adjacent sequences: A350682 A350683 A350684 * A350686 A350687 A350688

Keyword

nonn,hard,more

Author

M. F. Hasler, Jan 11 2022

Extensions

a(7) from M. A. Achterberg, Feb 10 2022

Status

approved