All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
MultiSquares (Posted on 2008-08-28) Difficulty: 4 of 5
A plane surface is marked with points in a square gridded format.

How many squares,
using the points as their vertices,
can be drawn within a grid of:
1. 6 x 6 points,
2. 7 x 7 points
and
3. n x n points?

In this 3 x 3 array:
   .  .  .
   .  .  .
   .  .  .  
          there are 6.
The 5th envelopes them all and
the 6th uses the outer midpoints 
of the grid as its vertices.

See The Solution Submitted by brianjn    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution Comment 2 of 2 |

There are (n-1)^2 1x1 squares, (n-2)^2 2x2 squares, ..., 1^2=1 nxn square.

Then there are diagonal squares of various slope. Categorizing the slopes by the Delta x and Delta y of the top left sloping side, Delta x can be anywhere from 1 to n-1, with Delta y being anywhere from 1 to n - 1 - DeltaX. The resulting tilted square then occupies DeltaX + DeltaY rows and columns, as the upper right sloping side of the square interchanges deltaX and deltaY, and can therefore be treated like an orthogonal square of side DeltaX + DeltaY.

So we get Sigma{r=1 to n-1}(r^2) + Sigma{dx=1 to n-1}Sigma{dy = 1 to n - 1 - dx}((n - (dx+dy))^2)

n         # of squares
1             0
2             1
3             6
4             20
5             50
6             105
7             196
8             336
9             540
10            825

DEFDBL A-Z
FOR n = 1 TO 10
 tot = 0
 FOR r = 1 TO n - 1
   tot = tot + r * r
 NEXT
 FOR dx = 1 TO n - 1
   FOR dy = 1 TO n - 1 - dx
       r = dx + dy
       tot = tot + (n - r) * (n - r)
   NEXT dy
 NEXT dx
 PRINT n, tot
NEXT

The On-Line Encyclopedia of Integer Sequences (Sloane) lists this as sequence A002415. One of its many definitions is

 a(n) = number of squares with corners on an n X n grid. See also A024206, A108279.
 
and its closed-form formula is

n^2*(n^2-1)/12

and they are called the 4-dimensional pyramidal numbers.

Actually, the program works just as well using:

DEFDBL A-Z
FOR n = 1 TO 10
 tot = 0
 FOR dx = 0 TO n - 1
   FOR dy = 1 TO n - 1 - dx
       r = dx + dy
       tot = tot + (n - r) * (n - r)
   NEXT dy
 NEXT dx
 PRINT n, tot
NEXT

corresponding to

Sigma{dx=0 to n-1}Sigma{dy = 1 to n - 1 - dx}((n - (dx+dy))^2)


 


  Posted by Charlie on 2008-08-28 12:50:02
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information