[seqfan] No right isosceles triangles in a square grid
Neil Sloane
njasloane at gmail.com
Fri Apr 22 12:28:03 CEST 2016
This list seems to have been quiet lately, so let
me mention a problem that was keeping me awake
last night, so I can go back to sleep confident that when I wake it
it will have been solved.
Take a square grid of n X n points. What is
the size of the largest subset S of these points
such that no three of the points of S form a right isosceles triangle?
That is, S must not contain 3 points A,B,C such that angle ABC
= 90 degrees, and |AB| = |BC|.
I am pretty sure that a(1)=1, a(2)=2, a(3)=4
from
XXX
OOO
OXO
and I think a(4)=6.
Wanted: enough terms to look this up in the OEIS
and to add it if it is not there.
This is in the same class of problems as A227133, and
there are several similar problem listed there in the cross-references.
An example of a forbidden triangle is
OBOO
OOOC
AOOO
OOOO
(Asymptotically it is known that a(n) = o(n^2),
but for any delta>0, for sufficiently large n, a(n) > n^(2-delta).)
Best regards
Neil
Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com
More information about the SeqFan
mailing list