The game of Quod

[Mitch Harris]

> From: Joshua Zucker [mailto:joshua.zucker at gmail.com] 
> 
> Sets of four points in the 3x3 case that form a square:
>  x
> xxx
>  x
> 
> There's only one square there, rotated 90 degrees.  There are only
> five points.  Does this make sense?
> 
> Then in the 4x4 case:
>  xx
> xxxx
> xxxx
>  xx
> 
> Looks like 5 squares of length 1, 4 squares of length sqrt(2), and 2
> squares of length sqrt(5), 11 total?  Yup.

Arghhh! Yes. My poor english skills. I didn't think of non-axis-parallel 
squares. The original source probably specified.

Anyway, in trying tp make sense of this I found the following related 
sequences:

  - squares on board with corners (i.e. not mutilated) is 4-dim pyramidal
numbers
     http://www.research.att.com/~njas/sequences/A002415

  - squares on board with corners -and- axis parallel (orthogonal) is sum
k^2
     http://www.research.att.com/~njas/sequences/A000330

  - squares on mutilated board, orthogonal (my faulty interpretation) 
(not in OEIS) (not particularly exciting)

  - rectangles, board not mutilated, orthogonal (sum k^3)
     http://www.research.att.com/~njas/sequences/A000537

  - rectangles, board not mutilated
     http://www.research.att.com/~njas/sequences/A085582

> On 12/18/06, Mitchell A. Harris <maharris at partners.org> wrote:
> > OK. That's what I think too. But is what I calculate below 
> make sense? It is
> > different from what you say comes from Ian Stewart's book. 
> How about just
> > that simplest case of 3x3? I think it is 5 but the Borris 
> polynomial (the
> > OEIS entry gives 1.
> > Any ideas?
> >
> >
> > On 12/18/06 6:17 PM, "Joshua Zucker" 
> <joshua.zucker at gmail.com> wrote:
> >
> > > Squares are sets of four spots on the nxn board that make a square
...
> > > does that help?
> > > --Joshua Zucker
> > >
> > >
> > > On 12/18/06, Mitch Harris <Harris.Mitchell at mgh.harvard.edu> wrote:
> > >>> From: Joshua Zucker [mailto:joshua.zucker at gmail.com]
> > >>>
> > >>> In Ian Stewart's latest book, he mentions the game of Quod. (Ch
7 of
> > >>> _How To Cut A Cake: and other mathematical conundrums_)
> > >>>
> > >>> One sequence of relevance to this game is the number of squares
in an
> > >>> nxn board with the four corners deleted.  He says that Denis
Borris
> > >>> found that there are (n^4 - n^2 - 48n + 84)/12 of them, which is
not
> > >>> in OEIS.
> > >>>
> > >>> He also says that Ken Duisenberg found the formula for the mxn
case
> > >>> (which would make a nice triangle for OEIS) but he doesn't give
the
> > >>> formula, nor a reference.  Anyone have a suggestion?
> > >>
> > >> Call me kooky (or slow) but a quick check to me says that the 3x3
board
> > >> with the 4 corners removed leaves 3^2 - 4 = 5 (unit) squares (and
unit
> > >> squares are the only ones that fit).
> > >>
> > >> And isn't the general idea just that the only 'bad' squares of
any size
> > >> k are those that include one of the corners (and for any k sided
squares
> > >> there are exactly 4 of these 'bad' squares)?
> > >>
> > >> Or formally
> > >>    Sum[(n-k)^2 - 4, {k, 0, n-2}] =   Sum[k^2 - 4, {k, 2, n}]
> > >>   =
> > >>    (2n^3 + 3n^2 - 23n + 18)/6
> > >>   =
> > >>    0, 5, 17, 38, 70, 115, 175...
> > >>
> > >> (which is also not in the OEIS)
> > >>
> > >> and the formula for nxm rectangles (and squares in them) has
formula
> > >> (for n<m)
> > >>
> > >>    Sum[(n - k)(m - k) - 4 , {k, 0, n - 2}]
> > >>   =
> > >>    (3m n^2 - n^3 + 3m n - 5n - 18m + 18)/6
> > >>
> > >> Please tell me where I've gone wrong.
> > >>
> > >> (Unfortunately I have no idea about the original problem.)
> > >>
> > >> Mitch