login
Symmetric array read by antidiagonals: T(n,k) (n>=1, k>=1) = maximal number of points that can be chosen in an n X k rectangular grid such that no three distinct points form an isosceles triangle.
3

%I #63 Dec 01 2016 01:33:04

%S 1,2,2,3,2,3,4,4,4,4,5,4,4,4,5,6,5,5,5,5,6,7,6,6,6,6,6,7,8,7,8,7,7,8,

%T 7,8,9,8,8,8,8,8,8,8,9,10,9,10,9,9,9,9,10,9,10

%N Symmetric array read by antidiagonals: T(n,k) (n>=1, k>=1) = maximal number of points that can be chosen in an n X k rectangular grid such that no three distinct points form an isosceles triangle.

%C It is conjectured that T(n,k) <= n+k-1.

%C The array is symmetric: T(n,k) = T(k,n).

%C The main diagonal T(n,n) appears to equal 2n-2 for n>1. (This diagonal is presently A271907, but if it really is 2n-2 that entry may be recycled.)

%C The triangle must have nonzero area (three collinear points don't count as a triangle).

%H Rob Pratt, <a href="/A271914/a271914.txt">Complete list of examples where T(n,k) != n+k-2 for 10 >= n >= k >= 2</a>. Note T(9,6) = T(6,9) = 12, which is n+k-3.

%F From _Chai Wah Wu_, Nov 30 2016: (Start)

%F T(n,k) >= max(n,k).

%F T(n,max(k,m)) <= T(n,k+m) <= T(n,k) + T(n,m).

%F T(n,1) = n.

%F T(n,2) = n for n > 3.

%F For n > 4, T(n,3) >= n+1 if n is odd and T(n,3) >= n+2 if n is even.

%F Conjecture: For n > 4, T(n,3) = n+1 if n is odd and T(n,3) = n+2 if n is even.

%F Conjecture: If n is even, then T(n,k) <= n+k-2 for k >= 2n.

%F (End)

%e The array begins:

%e 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...

%e 2, 2, 4, 4, 5, 6, 7, 8, 9, 10, ...

%e 3, 4, 4, 5, 6, 8, 8, 10, 10, 12, ...

%e 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...

%e 5, 5, 6, 7, 8, 9, 10, 12, 12, 14, ...

%e 6, 6, 8, 8, 9, 10, 11, 12, 12, 14, ...

%e 7, 7, 8, 9, 10, 11, 12, 13, 14, 16, ...

%e 8, 8, 10, 10, 12, 12, 13, 14, 16, 16, ...

%e 9, 9, 10, 11, 12, 12, 14, 16, 16, 18, ...

%e 10, 10, 12, 12, 14, 14, 16, 16, 18, 18, ...

%e ...

%e As a triangle:

%e 1,

%e 2, 2,

%e 3, 2, 3,

%e 4, 4, 4, 4,

%e 5, 4, 4, 4, 5,

%e 6, 5, 5, 5, 5, 6,

%e 7, 6, 6, 6, 6, 6, 7,

%e 8, 7, 8, 7, 7, 8, 7, 8,

%e 9, 8, 8, 8, 8, 8, 8, 8, 9,

%e 10, 9, 10, 9, 9, 9, 9, 10, 9, 10,

%e ...

%e Illustration for T(2,3) = 4:

%e XOX

%e XOX

%e Illustration for T(2,5) = 5:

%e XXXXX

%e OOOOO

%e Illustration for T(3,5) = 6 (this left edge + top edge construction - or a slight modification of it - works in many cases):

%e OXXXX

%e XOOOO

%e XOOOO

%e Illustration for T(3,6) = 8:

%e XXOOXX

%e OOOOOO

%e XXOOXX

%e Illustration for T(3,8) = 10:

%e OXXXXXXO

%e XOOOOOOX

%e XOOOOOOX

%e Illustration for T(6,9) = 12:

%e OXOOOOOOX

%e OOXXXXXXO

%e OOOOOOOOO

%e OXOOOOOOX

%e OXOOOOOOX

%e OOOOOOOOO

%e From _Bob Selcoe_, Apr 24 2016 (Start)

%e Two symmetric illustrations for T(6,9) = 12:

%e Grid 1:

%e X X O O O O O X X

%e O O O O O O O O O

%e O O O O O O O O O

%e O X X X O X X X O

%e X O O O O O O O X

%e O O O O O O O O O

%e Grid 2:

%e X O O O O O O O X

%e X O O O O O O O X

%e O O O O O O O O O

%e O X X X O X X X O

%e X O O O O O O O X

%e O O O O O O O O O

%e (Note that a symmetric solution is obtained for T(5,9) = 12 by removing row 6)

%e (End)

%Y Cf. A271910.

%Y Main diagonal is A271907.

%K nonn,tabl,more

%O 1,2

%A _Rob Pratt_ and _N. J. A. Sloane_, Apr 24 2016