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?
Per the below table the answer seems to be 6936.
The below program selects all sizes and orientations that would fit into a square of the given size and counts how many of them would, based on the length and orientation of its upper side or its upper left side (for tilted squares--positive slope), using each size/orientation's vertical and horizontal spans.
clearvars, clc
for n=1:50
ct=0;
for dx=1:n
for dy=0:n-1
xdiff=dx+abs(dy);
ydiff=xdiff;
if (n-xdiff+1)>0
incr=(n-xdiff+1)*(n-ydiff+1);
ct=ct+incr;
end
end
end
% disp([n ct])
fprintf('%2d %7d\n',n,ct)
end
internal
n squares
1 1
2 6
3 20
4 50
5 105
6 196
7 336
8 540
9 825
10 1210
11 1716
12 2366
13 3185
14 4200
15 5440
16 6936
17 8721
18 10830
19 13300
20 16170
21 19481
22 23276
23 27600
24 32500
25 38025
26 44226
27 51156
28 58870
29 67425
30 76880
31 87296
32 98736
33 111265
34 124950
35 139860
36 156066
37 173641
38 192660
39 213200
40 235340
41 259161
42 284746
43 312180
44 341550
45 372945
46 406456
47 442176
48 480200
49 520625
50 563550
The first three were verified by hand count. The first six were entered into the OEIS, where A002415 was found: 4-dimensional pyramidal numbers: a(n)=n^2*(n^2-1)/12, except that their n is one higher than ours, so we need (n+1)^2*((n+1)^2-1)/12.
Among other alternative uses for the series the OEIS gives:
a(n) is the number of squares of side length at least 1 having vertices at the points of an n X n unit grid of points (the vertices of an n-1 X n-1 chessboard). For example, on the 3 X 3 grid (the vertices of a 2 X 2 chessboard) there are four 1 X 1 squares, one (skew) sqrt(2) X sqrt(2) square, and one 3 X 3 square, so a(3)=6. On the 4 X 4 grid (the vertices of a 3 X 3 chessboard) there are 9 1 X 1 squares, 4 2 X 2 squares, 1 3 X 3 square, 4 sqrt(2) X sqrt(2) squares, and 2 sqrt(5) X sqrt(5) squares, so a(4) = 20.
Here the one unit difference is accounted for by considering n as the size of a row or column of an nxn chessboard, where the grid is (n+1)x(n+1).
|
|
Posted by Charlie
on 2021-09-03 12:23:16 |
Same answer
