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

Author

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

Keywords

• nonn
• more

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

Examples

			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
		

Links

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

Crossrefs

Cf. A271907, A227133.

Programs

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]