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?
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
soln - better version
