login
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

%I #15 Mar 20 2016 11:00:07

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

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

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

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

%e n, a(n), example of optimal S:

%e 1, 1, [1]

%e 2, 2, [1, 2]

%e 3, 4, [1, 3, 4]

%e 4, 6, [1, 2, 4, 5]

%e 5, 8, [2, 3, 5, 6]

%e 6, 10, [3, 4, 6, 7]

%e 7, 13, [1, 5, 7, 8, 10]

%e 8, 16, [1, 2, 7, 8, 10, 11]

%e 9, 20, [1, 3, 4, 9, 10, 12, 13]

%e 10, 24, [1, 2, 4, 5, 10, 11, 13, 14]

%e 11, 28, [2, 3, 5, 6, 11, 12, 14, 15]

%e 12, 32, [3, 4, 6, 7, 12, 13, 15, 16]

%e 13, 36, [4, 5, 7, 8, 13, 14, 16, 17]

%e 14, 40, [5, 6, 8, 9, 14, 15, 17, 18]

%e ...

%e For example, the line 5, 8, [2, 3, 5, 6] corresponds to the triangle

%e ....1....

%e ...0.1...

%e ..1.1.0..

%e .1.0.1.0.

%e 0.1.1.0.0

%e and the value a(5) = 8.

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

%Y This is a lower bound on A227308.

%Y Cf. A003002, A269745.

%K nonn,more

%O 1,2

%A _Warren D. Smith_ and _N. J. A. Sloane_, Mar 20 2016