Solution to the Holiday Puzzle

On Christmas Eve I posted a problem about "counting Squares" suggested by Joshua Zucker in response to my blog on the history of problems involving sums of squares.

Since I'm about to give the answer to that here, you might want to go read that post first in order not to have the puzzle spoiled.


The idea is to count the number of squares that could be made in a (n+1) by (n+1) array of dots as shown above. For reasons that reflect more on how my mind works than good mathematics, I have chosen to call the 3x3 array of lattice points a 2x2 square grid. Others may wish to add one to my n's etc.

First, a solution I'm pretty sure of. I'm pretty sure because it comes Neil Sloane's OEIS web page, and these guys are pretty good fact checkers. They give 1, 6, 20, 50, 105, 196, 336, 540, as the solutions for n= 1,2,...etc.

Now that the answer is out of the bag, I wanted to show how I arrived at a solution with a simple counting scheme, and then a recursive approach and a detail that I completely overlooked until Joshua sent me a note.

First, to steal from Sinatra, I do it my way.

After playing with the puzzle awhile, I noticed that for a nxn grid, there were exactly n squares that had all vertices on the outer edges.

There is always one that looks "aligned" to the grid, as below:

but the insight came when I realized that there would be n-1 more that were "tilted". In the 3x3 square there are two that look like this:

So in the 4x4 square grid, there was 1 aligned and 3 tilted squares that were inscribed. But of course for all the smaller grids inside, there were multiples of all the smaller grids.

So to count, for example, the number of squares in a 4x4 square grid of points, we know that there are 4 on the first shell, but on there are 2² ways to pick the upper left corner of a 3x3 grid inside this, and each of those grids have 3 squares that can be formed on the outside of each of these grids. Likewise there are 3² ways to pick a 2x2 grid inside the 4x4, and each of them contains 2 unique squares. and of course there are the final 4² ways to pick a 1x1 grid that each has only one square. Finding a total of 1(4) + 4(3) + 9(2) + 16(1) = 4+12+18+16 = 50.

In general this will produce the total for any level. Start at the n^th level and 1(n)+2²(n-1)+3²(n-2)... down to n²(1).
That's easy enough to write in summation notation,  so I leave it to the reader and move on to something a little more interesting.

A recursive way to count the square is to use a three column recursive process.  Folks who love spreadsheets could quickly extend this to huge values.   It uses the interesting fact, which completely escaped me, that the number of tilted squares at any level, is the same as the total number of squares at the previous level.

Grid Size .................. Aligned squares................... Tilted squares  ............... Total squares
1x1 ............................ 1 ²  ............................................... 0 .......................................1
2x2 ............................2²+1²..............................................1........................................6
3x3 ..................... 3²+2²+1²..............................................6........................................20
4x4....................4²+ 3²+2²+1²  .......................................20.......................................50
nxn                  Sigma n² ..................... total from (n-1)x(n-1)       ... sum of #'s on this row


This can lead quickly, I think, to realizing that the total after n levels is just the sum of all the square based pyramids up to the one with n² in the base,  In a table that looks like:
Grid size       Squares
1       .............   1
2  ................... 2² + 1² + previous total =4+1+1=6
3  ....................3²+2²+1² + Previous total = 9+4+1+6=20

 On thinking about the number of tilted squares at each new level, the number of NEW tilted squares at the n+1 grid will be (n² - (n-1)²) + 2[(n-1)² - (n-2)²] + 3[(n-2)² - (n-3)²]...  and these differences turn into the Gnomens that the Greeks knew were intimately tied to the squares.  For them this expression would probably look like (2n-1) + 2(2n-3) + 3(2n-5) + .... +(n-1)(1) .

For younger students who have not experienced this, the gnomen may be thought of as just the odd numbers arranged in an L, and the sequence of odds will always produce a square number.  Below I have 1+3+5 making a 3x3 square of 9 units.

For the 5x5 square grid, the number of NEW tilted squares that occurs will be 7+2(5)+3(3)+4(1)=20
Can we make these Gnomens give us the square based pyramids we seek?  It seems we can, for if we spread them out we have 7 + 5 + 5 + 3 + 3 + 3 + 1 + 1+ 1 + 1... and regrouping them as (7+5+3+1) + (5 + 3 + 1) + (3 + 1) + 1  =16 + 9 +4 + 1 = 30 we have a square based pyramid for a 4x4 base.
 The number of NEW tilted squares exactly matches the old number of non-tilted squares, and thus the total of all the squares at the previous level.


Joshua wrote me with a more combinatorial solution to counting the tilted squares and I repost his words below for fear I would not do justice with a summary.

---------------------------------------------------------------------

Here's an almost-rigorous proof of one amazingly compact formula for the total number of tilted squares.  At least ,if I understand my own logic correctly, this counts all the squares whose sides are not parallel to the axes, in a grid of area n^2 (and thus of n+1 by n+1 dots).

Any tilted square has its vertices on four different rows.  But once we choose three of them, in order from bottom to top let's say, the shape of the square is fixed.  So:

We choose the 3 rows.  There are (n+1) choose 3 ways to do this.
Let's call them a, b, c in order. At this point we know that the
square is based on the vector (b-a, c-b).

Then we have to choose a location for the top point; the rest is then
determined by those vectors.  There are n+1 choices for that top point
in its row.  But some of those don't work, because the vectors will
make things stick out one way or another.

But the total horizontal extent of the square is (c-a).  So we are
going to have (n+1) - (c-a) places where the top point will work.

This seems like it's going to lead to a big ugly summation, maybe even a double sum or possibly triple.  But there is symmetry!

There are (n-1)*1 ways where c - a = 2, because we choose the top row
in n-1 ways, and then the middle row in 1 way, since there's only 1
more row in the distance of 2.
There are (n-2)*2 ways where c - a = 3, because we choose the top row
in n-2 ways, and then the middle row has 2 possibilities in between.
And so on, up to 1*(n-1) ways where c-a = n.

In other words, the number of ways for 2 and n are the same, for 3 and
n-1, and so on, since this is a symmetric list.  So the average is
(n+2)/2.

And (n+1) - (n+2)/2 = n/2.  (A shame that this much algebra had to be involved to get that elegant n/2.)  So, there are (n+1 choose 3) ways to pick three rows, and on average each of those leads to n/2 tilted squares.

So there are (n+1 choose 3) * n/2 tilted squares in the grid. Add your n(n+1)(2n+1)/6 if you want the grand total.

QED.

Now onward to (n choose 2) * (n+1 choose 2) / 3... which is (without very much work) clearly algebraically equivalent, and a combinatorial proof seems within reason for that formula as well.  I have a few other equivalent formulas to think about too ...

Incidentally, all of these were discovered by some brute-force summations and then various algebraic or finite-differences tricks to find the simpler forms, and then the combinatorial approaches were found as explanations of the surprisingly simple formulas.

Thanks Joshua, both for the original problem, and a stimulating solution.