[seqfan] Re: How many squares can you make from n points in the plane?

[Neil Sloane]

Update on A051602

The original definition allowed the points to be anywhere, and the sequence
gave 16 terms of  which only the first 6 (which were trivial) were known to
be correct.  So I changed the definition to require the points to be grid
points. Now there seems a much better chance of getting 16 terms exactly.

However, there is still some uncertainty, because Sean's program only
searches in a bounded portion of the grid. I don't know the details, but
now surely we can get more than 6 or 7 exact terms.

In the comments in A051602 I use b(n) for the unrestricted case, (that is,
the original definition), and I will add the two proofs from hv and Benoit
that b(7) = 3 there.

Best regards
Neil

Neil J. A. Sloane, Chairman, 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 Wed, Sep 29, 2021 at 8:18 AM Benoît Jubin <benoit.jubin at gmail.com> wrote:

> Another proof that a(7) = 3 (that is, a planar figure with 7 points
> contains at most 3 squares, and there are figures realizing this
> number):
>
> First, note that two different squares cannot share three vertices.
> If a 7-point figure contains (at least) 3 squares, then by simple
> counting there is a pair of squares sharing two vertices.  There are
> only two possibilties:
> (1) they share an edge;
> (2) an edge of one of them is a diagonal of the other.
> None of these 6-point figures contain a third square.  Therefore, if
> the 7-point figure contains other squares, they are formed from a 7th
> point, and three points in the 6-point figure (and not all three
> belonging to the same square of that figure, by the preliminary
> remark).  The triples of points in these 6-point figures that are in
> square-position are few: two (one up to symmetry) in case (1), and
> three (two up to symmetry) in case (2).  They lead to the two 7-point
> 3-square configurations (since one of the cases in (2) yields the same
> figure as the one from (1)).  None of these two figures contain a
> fourth square.
>
> Benoît
>
> On Wed, Sep 29, 2021 at 6:54 AM <hv at crypt.org> wrote:
> >
> > I should have said: I worked below _without_ the assumption that the
> > points had integer coordinates, so if accurate this proves something
> > slightly stronger. _With_ that assumption, it would not have been
> > safe to assume we can scale any arrangement to make the smallest
> > square be a unit square.
> >
> > Hugo
> >
> > I wrote:
> > :Neil Sloane <njasloane at gmail.com> wrote:
> > ::It seems that surprisingly little is known - see A051602. Even a(7) is
> an
> > ::open question, although it is easy to see that a(7) >= 3.
> > :
> > :Unless I'm missing something, the 7-point case doesn't seem too hard.
> > :
> > :Fix 4 points on the standard unit square, and wlog assume this is the
> > :smallest square in the final combination. There are then four
> > :possibilities.
> > :
> > :A) There's another square of the same size, sharing two points with the
> > :first. Then the 7th point can only give us a third square in two
> > :symmetrically placed ways, of side sqrt(2). No fourth is possible.
> > :
> > :B) There's another square of the same size, sharing one point with the
> > :first. Then all 7 points are accounted for. Any third square must use
> > :two points from each of the existing two squares, so again can only
> > :have a side of sqrt(2); that is possible, but there can't be a fourth.
> > :
> > :C) There's another square of a different size, sharing two points with
> > :the first; this can only have side sqrt(2). The only ways to select
> > :three of those points such that the 7th point can be added to give a
> > :square in each case reduce us to case A or B.
> > :
> > :D) There's another square of a different size, sharing one point with
> > :the first. All points are accounted for, and any additional square
> > :must share two points with each of the first two squares; but then
> > :any such third square must reduce us to case A or C.
> > :
> > :So the possibilities are:
> > :
> > :.XX
> > :XXX
> > :XX.
> > :
> > :and
> > :
> > :.X.
> > :XXX
> > :XXX
> > :
> > :Hugo
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>