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.
Assumptions:
- the bottom row is n solid blocks.
- maximum perimeter is when 1xn columns alternate with 1x1 columns
- wlog let leftmost column be a solid 1xn; the rightmost will either be 1xn or 1x1 depending on whether n is even or odd
The analysis below leads to the following formulae:
f_even(n) = n^2 + n + 2 if n is even
f_odd(n) = n^2 + 2n + 1 if n is odd
1 4
2 8
3 16
4 22
5 36
6 44
7 64
8 74
9 100
10 112
11 144 (not in Sloane's oeis)
Example for n = 4:
X X
X X
X X
XXXX I count 22
For evens:
2n for the left side and bottom
(n-1)*(n-1) inside vertical walls
1 right side vertical wall
(n/2) tops of towers
(n/2) bottoms of valleys
Total: 2n + n^2 - 2n + 1 + 1 + n/2 + n/2
= n^2 + n + 2
For odds:
3n for the left side, right side, and bottom
(n-1)*(n-1) inside vertical walls
(n/2 + 1/2) tops of towers
(n/2 - 1/2) bottoms of valleys
Total: 3n + n^2 - 2n + 1 + (n/2 + 1/2) + (n/2 - 1/2)
= n^2 + 2n + 1
-----
def count(n):
if n%2 == 0:
return int(n**2 + n + 2)
else:
return int(n**2 + 2*n + 1)
for n in range(1,12):
print(n, count(n))
|
|
Posted by Larry
on 2024-02-23 15:48:38 |
Formula
