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

Home > Just Math
Grid squares (Posted on 2021-09-03) Difficulty: 3 of 5
How many unique squares can be drawn inside a 16 x 16 square if their vertices must lie on a grid (lattice) of integer points? The sides of these smaller squares need not be parallel to the sides of the large square. Any vertex or edge on the boundary of the large square is counted as inside the large square. Bonus: can you generalize this to an n x n square?

Note: This is not a packing problem. These squares can overlap. How many such squares are there?

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
soln - better version | Comment 2 of 7 |


We start with a catalog of possible squares. We define a "drawing rule"
 (i,j) that represents the x & y displacement between the 1st and 
second vertices. Let i range from 1 to 16, and j from 0 to 15.  
A square is formed by successive displacements from an (x,y) 
vertex: (i,j) (-j,i), (-i,-j), and (j,-i), to get back to the 
original vertex. This covers all possible squares. For each rule, 
we count how many squares fit inside the boundaries. The smallest 
square is (i,j) = (1,0) and there are 256. The largest, a 16x16 square is 
(i,j)= (16,0) and there is 1. As all (i,j) shapes are considered, 
we find that i+j=k is the governing number: For any k, [k (n+1-k)^2] of 
them may be drawn. The reason for this is that as the number of ways to 
make i+j grows linearly, the number of grid points they may be drawn 
from goes as n+1-k squared.

The table below lists how many i+j=3 squares may be drawn in each row, 
showing the min and max column in each row. When no square can be drawn 
in a row, the range is listed as "99 - -1". The are k=3 types of 
squares: (3,0),(2,1), (1,2) and (n+1-k)^2 = 14^2 = 196 of each fit 
in the 16x16 grid.

The full table is here list123.txt and the program that generates 
it is here sf123.f. 

( i  j) row  col min-max  tot  
=========================================
( 3, 0)   0     0 - 13    14
( 3, 0)   1     0 - 13    14
.
.
.
( 3, 0)  13     0 - 13    14
( 3, 0)  14    99 - -1     0
( 3, 0)  15    99 - -1     0 
----------------total for shape (3,0) 196

( 2, 1)   0     1 - 14    14
( 2, 1)   1     1 - 14    14
.
.
.
( 2, 1)  13     1 - 14    14
( 2, 1)  14    99 - -1     0
( 2, 1)  15    99 - -1     0
----------------total for shape (2,1) 196


( 1, 2)   0     2 - 15    14
( 1, 2)   1     2 - 15    14
.
.
.
( 1, 2)  13     2 - 15    14
( 1, 2)  14    99 - -1     0
( 1, 2)  15    99 - -1     0
----------------total for shape (1,2) 196

etc...

The program also summarized the whole collection of (i,j) squares
in one table as shown below. 6936 total squares are possible in 
the 16x16 case. 


      1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
    ----------------------------------------------------------------
  0 256 225 196 169 144 121 100  81  64  49  36  25  16   9   4   1
  1 225 196 169 144 121 100  81  64  49  36  25  16   9   4   1   0
  2 196 169 144 121 100  81  64  49  36  25  16   9   4   1   0   0
  3 169 144 121 100  81  64  49  36  25  16   9   4   1   0   0   0
  4 144 121 100  81  64  49  36  25  16   9   4   1   0   0   0   0
  5 121 100  81  64  49  36  25  16   9   4   1   0   0   0   0   0
  6 100  81  64  49  36  25  16   9   4   1   0   0   0   0   0   0
  7  81  64  49  36  25  16   9   4   1   0   0   0   0   0   0   0
  8  64  49  36  25  16   9   4   1   0   0   0   0   0   0   0   0
  9  49  36  25  16   9   4   1   0   0   0   0   0   0   0   0   0
 10  36  25  16   9   4   1   0   0   0   0   0   0   0   0   0   0
 11  25  16   9   4   1   0   0   0   0   0   0   0   0   0   0   0
 12  16   9   4   1   0   0   0   0   0   0   0   0   0   0   0   0
 13   9   4   1   0   0   0   0   0   0   0   0   0   0   0   0   0
 14   4   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0
 15   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
The total is 6936


If we look at the results for n=15 as well, we see the pattern: 
lord@rabbit resolve % q
  n? 
15

      1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
  0 225 196 169 144 121 100  81  64  49  36  25  16   9   4   1
  1 196 169 144 121 100  81  64  49  36  25  16   9   4   1   0
  2 169 144 121 100  81  64  49  36  25  16   9   4   1   0   0
  3 144 121 100  81  64  49  36  25  16   9   4   1   0   0   0
  4 121 100  81  64  49  36  25  16   9   4   1   0   0   0   0
  5 100  81  64  49  36  25  16   9   4   1   0   0   0   0   0
  6  81  64  49  36  25  16   9   4   1   0   0   0   0   0   0
  7  64  49  36  25  16   9   4   1   0   0   0   0   0   0   0
  8  49  36  25  16   9   4   1   0   0   0   0   0   0   0   0
  9  36  25  16   9   4   1   0   0   0   0   0   0   0   0   0
 10  25  16   9   4   1   0   0   0   0   0   0   0   0   0   0
 11  16   9   4   1   0   0   0   0   0   0   0   0   0   0   0
 12   9   4   1   0   0   0   0   0   0   0   0   0   0   0   0
 13   4   1   0   0   0   0   0   0   0   0   0   0   0   0   0
 14   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0
The total is 5440

All cases are here. lista123.txt

We see the result for an n is the series sum:
a(n) = SUM(i=1->n) [(n+1-i) i^2]

Running cases n=1,16 gives

lord@rabbit resolve %
   n  =  1   2   3   4   5    6    7    8    9   10   
11   12   13   13   15   16
  a(n) = 1   6  20  50 105  196  336  540  825 1210 
1716 2366 3185 4200 5440 6936

To gauge this series as a possible closed polynomial form, 
we take differences:

 1   6  20  50 105  196  336  540  825 1210 1716 2366 3185 4200 5440 6936
   5  14  30  55  91  140  204  285  385  506  650  819 1015 1240 1496
     9  16  25  36  49   64   81  100  121  144  169  196  225  256
      7   9  11  13  15   17   19   21   23   25   27   29   31
        2   2   2   2   2    2    2    2    2    2    2    2

This indicates a(n) is a 4th order polynomial. 

a(n) = A + B n + c n^2 + D n^3 + E n^4

We can use the first 5 a(n) values to solve 5 equations in 5 unknowns 
using matrix determinants. The denominator matrix has rows:

1^0 1^1 1^2 1^3 1^4              
2^0 2^1 2^2 2^3 2^4
3^0 3^1 3^2 3^3 3^4      
4^0 4^1 4^2 4^3 4^4 
5^0 5^1 5^2 5^3 5^4

= 

  1.   1.   1.   1.   1.
  1.   2.   4.   8.  16.
  1.   3.   9.  27.  81.
  1.   4.  16.  64. 256.
  1.   5.  25. 125. 625.

The determinant of this matrix is del = 228 (program here de123.f)

Each coefficient is found in the standard way: substituting the 
column of constant a(n) solutions 
for a column in the matrix above and dividing by del: e.g. 
The 2nd n^1 coefficient is found by taking the determinant
of 

    1.      1.      1.      1.      1.
    1.      6.      4.      8.     16.
    1.     20.      9.     27.     81.
    1.     50.     16.     64.    256.
    1.    105.     25.    125.    625.

which is 48. Dividing by del gives B= 1/6. 
All calculations de123.f for A to E are here de123.txt. 
The result is this polynomial:
a(n) = (n^4 + 4n^3 + 5n^2 + 2n)/12   (1)

Looking up the series in OEIS, we find 
it is A002415 https://oeis.org/A002415

Form (1) may also be written as 
a(m) = m^2(m^2-1)/12, where m=n+1

This problem is sometime called "The Number of Squares on a Geoboard" 
problem https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1949-8594.1979.tb09466.x
and its general solution above is also known 
as "The Four-dimensional Pyramidal Numbers"

This is also the solution to several other enumeration problems, 
such as the number of ways to put 2 parentheses around n terms. 
For n=2, we have 6 ways: 

((a))b, ((a)b), ((ab)), (a)(b), (a(b)), a((b)).

Edited on September 3, 2021, 9:56 am
  Posted by Steven Lord on 2021-09-03 09:08:35

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 (0)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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