[seqfan] Re: No right isosceles triangles in a square grid

Rob Pratt Rob.Pratt at sas.com
Sat Apr 23 19:05:07 CEST 2016


Here are optimal solutions for the exceptional cases:

X X
O O
X X

X O X
X O X
O O O
O O O
X O X
X O X

X X O
O O X
O O X
O O X
O O X
O O X
O O X
X X O

X O O X X
O X O O O
O X O O O
O X O O O
O X O O O
O X O O O
O X O O O
X O O X X

X O O X X O
O X O O O O
O X O O O O
O X O O O O
O X O O O O
O X O O O O
O X O O O O
X O O X X O
O O O O O O

O X O X X O X O
O O O O O O O O
X O O O O O O X
X O O O O O O X
O O O O O O O O
X O O O O O O X
X O O O O O O X
O O O O O O O O
O X O X X O X O

X X O
O O X
O O X
O O X
O O X
O O X
O O X
O O X
O O X
X X O

X O O X X
O X O O O
O X O O O
O X O O O
O X O O O
O X O O O
O X O O O
O X O O O
O X O O O
X O O X X

X X O O X X O
O O O O O O X
O O O O O O X
O O O O O O X
O O O O O O X
O O O O O O X
O O O O O O X
O O O O O O X
O O O O O O X
X X O O X X O

O X X O O O X X O
O O O O O O O O O
O O X X O X X O O
O O O O O O O O O
O O O O O O O O O
X O O O O O O O X
O O O O O O O O O
O O O O O O O O O
X X O O O O O X X
O O X X O X X O O

-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil Sloane
Sent: Saturday, April 23, 2016 12:37 AM
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Subject: [seqfan] Re: No right isosceles triangles in a square grid

Rob,
Wow!  So the problem is more interesting than I thought.

I would like to see your optimal solutions, if you would care to send them to me.

And how about submitting the optimal solutions for the (m,n) problem as a new sequence?  (Could be an infinite square array read by anti-diagonals, or a triangle read by rows, whatever you want)

Then there is the question: "Show that if you take any m+n points in an m X n grid, some three of them form an isosceles triangle".

A Putman or Math Olympiad problem, maybe??   Where are
our young hotshots when we need them?


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


On Fri, Apr 22, 2016 at 11:59 PM, Rob Pratt <Rob.Pratt at sas.com> wrote:

> For (m,n) with 10 >= m >= n >= 2, the only exceptions are
> {(3,2),(6,3),(8,3),(8,5),(9,6),(9,8),(10,3),(10,5),(10,7),(10,9)},
> where the maximum is instead m + n - 1.
>
> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil
> Sloane
> Sent: Friday, April 22, 2016 7:01 PM
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Subject: [seqfan] Re: No right isosceles triangles in a square grid
>
> Looking at the isosceles-triangle avoiding problem, but for an m X n
> rectangular grid, where m>1, n>1, and without much data, I wildly
> conjecture that the answer is m+n-2.
> And that this can be achieved by taking the left edge and the top
> edge, removing the intersection, and then moving Xs in the top row
> down a bit to avoid any Pythagorean accidents.
>
> Can anyone supply some more data for the rectangular case?
>
> 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
>
>
> On Fri, Apr 22, 2016 at 6:15 PM, <israel at math.ubc.ca> wrote:
>
> > That comment would work for the case of right isosceles triangles
> > (A271906), but there it looks like A271906(n) = 3n-7 for n >= 6.
> >
> > I can confirm that A271906(11) >= 26, with a solution
> >     0     0     1     0     0     0     0     0     0     0     1
> >     1     0     1     0     0     0     0     0     0     0     1
> >     1     0     0     0     0     0     0     0     0     0     1
> >     0     0     0     0     1     1     0     0     0     0     1
> >     0     0     0     1     0     0     0     0     0     0     1
> >     0     0     0     1     0     0     0     0     0     0     1
> >     0     0     0     0     0     0     0     0     0     0     1
> >     0     0     0     0     0     0     0     0     0     0     1
> >     0     0     0     0     0     0     0     0     0     1     0
> >     0     0     0     0     0     0     0     0     1     0     0
> >     1     1     1     1     1     1     1     1     0     0     0
> >
> > and A271906(12) >= 29, with a solution
> >
> >     0     0     0     0     1     1     1     1     1     1     1     1
> >     0     0     0     1     0     0     0     0     0     0     0     0
> >     0     0     1     0     0     0     0     0     0     0     0     0
> >     0     1     0     0     0     0     0     0     0     0     0     0
> >     1     0     0     0     0     0     0     0     0     0     0     0
> >     1     0     0     0     0     0     0     0     1     0     0     0
> >     1     0     0     0     0     0     0     0     1     0     0     0
> >     1     0     0     0     0     0     0     0     0     0     1     0
> >     1     0     0     0     0     1     1     0     0     0     0     0
> >     1     0     0     0     0     0     0     0     0     0     0     1
> >     1     0     0     0     0     0     0     1     0     0     0     1
> >     1     0     0     0     0     0     0     0     0     1     1     0
> >
> > I'm not sure that these are optimal, but my searches for better
> > solutions have come up empty so far.
> >
> > Cheers,
> > Robert
> >
> >
> > On Apr 22 2016, Rob Pratt wrote:
> >
> > This comment seems wrong; " By using two edges of the grid minus
> > their
> >> intersection we get a(n) >= 2n-2. - N. J. A. Sloane, Apr 22 2016"
> >>
> >> For example, the cells (1,5), (4,1), and (9,1) lie in such a set
> >> but form an isosceles triangle.
> >>
> >> -----Original Message----- From: SeqFan [mailto:
> >> seqfan-bounces at list.seqfan.eu] On Behalf Of Neil Sloane Sent:
> >> Friday, April 22, 2016 2:50 PM To: Sequence Fanatics Discussion
> >> list < seqfan at list.seqfan.eu> Subject: [seqfan] Re: No right
> >> isosceles triangles in a square grid
> >>
> >> If you did not find any clever solutions for n <= 11, I bet we have
> >> a(n) =
> >> 2n-2 for all n>1.
> >>
> >> 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
> >>
> >>
> >> On Fri, Apr 22, 2016 at 1:35 PM, Giovanni Resta
> >> <g.resta at iit.cnr.it>
> >> wrote:
> >>
> >> Il 22/04/2016 17:34, Neil Sloane ha scritto:
> >>>
> >>> 1, 2, 4, 6, 8, 10, 12, 14, 14, 16, 20
> >>>>
> >>>>>
> >>>>> Could there be a typo? Did you mean to say
> >>>>
> >>>> Yes, sorry. I did make a mess merging results from Mathematica,
> >>> lp_solve and cplex.
> >>> It is 1,2,4,6,8,10,12,14,16,18 (I'm checking again a(11)=20
> >>> because I deleted the result),  i.e.,  it seems simply a(1)=1 and
> >>> a(n)=2n-2 up to a(10).
> >>>
> >>> I'm going to check again the results when I prepare the pictures.
> >>> Sorry for the error,
> >>>
> >>> Giovanni
> >>>
> >>> --
> >>> Seqfan Mailing list - http://list.seqfan.eu/
> >>>
> >>>
> >> --
> >> Seqfan Mailing list - http://list.seqfan.eu/
> >>
> >> --
> >> Seqfan Mailing list - http://list.seqfan.eu/
> >>
> >>
> >>
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>

--
Seqfan Mailing list - http://list.seqfan.eu/



More information about the SeqFan mailing list