|
%I #30 May 02 2016 10:10:50
%S 1,2,4,6,9,11,14,17,20,23,26
%N 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.
%C S must not contain 3 points A,B,C such that angle ABC = 90 degrees and |AB| = |BC|.
%C For example, this configuration is forbidden:
%C O B O O
%C O O O C
%C A O O O
%C O O O O
%C a(12) >= 29. - _Robert Israel_, Apr 22 2016
%C 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
%H Giovanni Resta, <a href="/A271906/a271906.png">Illustration of a(3)-a(11)</a>
%H Giovanni Resta, <a href="/A271906/a271906_1.png">Illustration of lower bounds on a(12)-a(15)</a>
%e Illustration for a(3) = 4:
%e X X X
%e O O O
%e O X O
%e Illustration for a(8) = 17:
%e O X O O O O O X
%e X O O O O O O X
%e O O O X O O O X
%e O O X O O O O X
%e O O O O O O O X
%e O O O O O O O X
%e O O O O O O X O
%e X X X X X X O O
%t 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]
%Y Cf. A271907, A227133.
%K nonn,more
%O 1,2
%A _Giovanni Resta_ and _N. J. A. Sloane_, Apr 22 2016
|
