An assemblage of unit squares is in the form of n towers with heights 1,2,...,n forming a polyomino.
Here are two possible examples for n=4:
Find a formula for the largest possible perimeter of such a polyomino.
The program counts
- 2*n for the horizontal sections of the perimeter (top and bottom).
- sum of first and last, for the left and right edges.
- sum of the differences between adjacent towers for the remaining vertical sections.
clearvars,clc
b=[];
for n=1:11
orders=perms(1:n);
best=0; bestOrder=[];
for i=1:length(orders)
order=orders(i,:);
peri=2*n+order(1)+order(end) ...
+sum(abs(order(1:end-1)-order(2:end)));
if peri>best
best=peri;
bestOrder=order;
end
end
b(end+1)=best;
fprintf('%2d %3d\n',n,best)
fprintf('%3d ',bestOrder)
fprintf('\n\n')
end
b
shows for n = 1 to 11,
first row: n and the highest perimeter,
second row: the sequence of heights of the towers to get that perimeter. (There may be others -- certainly the reverse of each).
1 4
1
2 8
2 1
3 14
3 1 2
4 20
4 2 1 3
5 28
5 2 4 1 3
6 36
6 3 2 5 1 4
7 46
7 3 6 2 5 1 4
8 56
8 4 3 7 2 6 1 5
9 68
9 4 8 3 7 2 6 1 5
10 80
10 5 4 9 3 8 2 7 1 6
11 94
11 5 10 4 9 3 8 2 7 1 6
b =
4 8 14 20 28 36 46 56 68 80 94
The bottom line summarizes all eleven maximum perimeters, so I could paste the list into the OEIS. That led to sequence A265284,
The Formula section of A265284 lists conjectured formulae as:
a(n) = (2*n^2+12*n-(-1)^n+1)/4 for n>0.
a(n) = (n^2+6*n)/2 for n>1 and even.
a(n) = (n^2+6*n+1)/2 for n odd.
a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4) for n>4.
G.f.: (1+2*x-x^4) / ((1-x)^3*(1+x)).
The two that apply only to odd or even could be combined into
ceil((n^2+6*n)/2)
and serve as the best answer to this puzzle.
|
|
Posted by Charlie
on 2024-02-23 13:01:43 |
computer-aided solution
