Newsgroups: rec.puzzles
From: hoey@pooh.tec.army.mil (Dan Hoey)
Date: 1995/12/09
Subject: Re: Geoboard squares [spoiler]

Bill Graham (Bill_Gra...@cmug-la.org) wrote:

: Geoboards are often used in elementary schools. They are usually
: plastic with protruding pegs in a square grid. You can loop rubber
: bands around the pegs to make various shapes....  How many squares
: can be formed by using the dots as the vertices (corners) of the
: squares?

I answered this a few years back, but I don't think it's in the
archives.  Perhaps that is because I am unwilling for my writing to
be used without attribution.

On the n x n board, consider k in {2,3,...,n}.  There are (n-k+1)^2
ways of placing a k x k square with edges parallel to the edges of
the board.  Consider the 4(k-1) pegs that form the perimeter of such
a square.  Any set of four pegs equally spaced around the perimeter
forms the corners of a square, making k-1 squares formed by those
pegs.  Conversely, given any square formed by pegs on the board, take
the smallest containing square with edges parallel to the edges of the
board; the given square will have its corners evenly spaced around the
periphery of the containing square.  So we count all squares in this
way.

We want the sum, for k in {2,3,...,n}, of (k-1)(n-k+1)^2.  Let
t=n-k+1; this is the sum, for t in {1,2,...,n-1}, of
t^2(n-t) = nt^2 - t^3.

My handy table of Bernoulli polynomials tells me that the sum for t in
{1,...,n-1} of t^2 is n(n-1)(2n-1)/6 and the sum for t in {1,...,n-1}
of t^3 is n^2(n-1)^2/4.

So the answer is n^2(n-1)(2n-1)/6 - n^2(n-1)^2/4 = n^2 (n^2 - 1) / 12.
For n=4 this is 20; for n=5 this is 50.

Nobody answered the ObPuzzles:

Easy: How many equilateral triangles are formed by a triangular array
      of side n?  How many regular hexagons in a hexagonally-shaped
      triangular array of side n?

Hard: How many cubes are formed by a three-dimensional cube with n
      points on an edge.

Dan Hoey                            posted and e-mailed
Hoey@AIC.NRL.Navy.Mil