A271906 Size of the largest subset S of the points of an n X n square grid such that no three of the points of S form a right isosceles triangle.

1, 2, 4, 6, 9, 11, 14, 17, 20, 23, 26

Offset

1,2

Comments

S must not contain 3 points A,B,C such that angle ABC = 90 degrees and |AB| = |BC|.

For example, this configuration is forbidden:

O B O O

O O O C

A O O O

O O O O

a(12) >= 29. - Robert Israel, Apr 22 2016

a(13) >= 32, a(14) >= 36, a(15) >= 38 (see pictures in Links). Note that a(14) >= 36 breaks the pattern of increasing by 3 at each step. - Giovanni Resta, Apr 23 2016

Links

Table of n, a(n) for n=1..11.

Giovanni Resta, Illustration of a(3)-a(11)

Giovanni Resta, Illustration of lower bounds on a(12)-a(15)

Example

Illustration for a(3) = 4:
   X X X
   O O O
   O X O
Illustration for a(8) = 17:
   O X O O O O O X
   X O O O O O O X
   O O O X O O O X
   O O X O O O O X
   O O O O O O O X
   O O O O O O O X
   O O O O O O X O
   X X X X X X O O

Mathematica

d[n_, a_, b_] := Block[{x1, y1, x2, y2}, x1 = Mod[a-1, n]; y1 = Floor[(a-1)/n]; x2 = Mod[b-1, n]; y2 = Floor[(b-1)/n]; (x1-x2)^2 + (y1-y2)^2]; isorQ[n_, a_, b_, c_] := Block[{k = Sort[{d[n, a, b], d[n, b, c], d[n, a, c]}]}, k[[1]] == k[[2]] && 2 k[[1]] == k[[3]]]; sol[n_] := sol[n] = Block[{m, L={}, nv=n^2, ne}, Do[If[ isorQ[n, x, y, z], AppendTo[L, {x, y, z}]], {x, n^2}, {y, x-1}, {z, y-1}]; ne = Length@L; m = Table[0, {ne}, {nv}]; Do[m[[i, L[[i]]]] = 1, {i, ne}]; Quiet@ LinearProgramming[ Table[-1, {nv}], m, Table[{2, -1}, {ne}], Table[{0, 1}, {nv}], Integers]]; a[n_] := Total[sol[n]]; Do[Print@ MatrixForm@ Partition[ sol@n, n], {n, 6}]; Array[a, 6]

Crossrefs

Cf. A271907, A227133.

Sequence in context: A274214 A276223 A288468 * A050502 A293956 A022760

Adjacent sequences: A271903 A271904 A271905 * A271907 A271908 A271909

Keyword

nonn,more

Author

Giovanni Resta and N. J. A. Sloane, Apr 22 2016

Status

approved