A269746 Maximal number of 1's in an equilateral triangle of 0's and 1's with n points on each side, the entries being constant on vertical lines, with property that no three 1's form a triangle with sides parallel to the edges of the triangle.

1, 2, 4, 6, 8, 10, 13, 16, 20, 24, 28, 32, 36, 40

Offset: 1

Author

Warren D. Smith and N. J. A. Sloane, Mar 20 2016

Keywords

• nonn
• more

Comments

The triangle is oriented with apex at the top and horizontal base.

Label the entries in the top left and right edges with the numbers 1 through 2n-1, and let S denote the subset of [1..2n-1] where these edges contains 1's. Then the matrix has the no-subtriangle property iff S contains no three-term arithmetic progression.

Examples

			n, a(n), example of optimal S:
1, 1, [1]
2, 2, [1, 2]
3, 4, [1, 3, 4]
4, 6, [1, 2, 4, 5]
5, 8, [2, 3, 5, 6]
6, 10, [3, 4, 6, 7]
7, 13, [1, 5, 7, 8, 10]
8, 16, [1, 2, 7, 8, 10, 11]
9, 20, [1, 3, 4, 9, 10, 12, 13]
10, 24, [1, 2, 4, 5, 10, 11, 13, 14]
11, 28, [2, 3, 5, 6, 11, 12, 14, 15]
12, 32, [3, 4, 6, 7, 12, 13, 15, 16]
13, 36, [4, 5, 7, 8, 13, 14, 16, 17]
14, 40, [5, 6, 8, 9, 14, 15, 17, 18]
...
For example, the line 5, 8, [2, 3, 5, 6] corresponds to the triangle
....1....
...0.1...
..1.1.0..
.1.0.1.0.
0.1.1.0.0
and the value a(5) = 8.
It is a plausible conjecture that any optimal solution S here is also an optimal solution to the square grid version in A269745, and vice versa. (The square grid being obtained by reflecting the triangle in its base.)
		

Crossrefs

This is a lower bound on A227308.

Cf. A003002, A269745.