A282939 - OEIS

%I #23 Jun 08 2021 15:07:10

%S 0,4,4,6,8,12,12,14,16,20,20,22,24,28,28,30,32,36,36,38,40,44,44,46,

%T 48,52,52,54,56,60,60,62,64,68,68,70,72,76,76,78,80,84,84,86,88,92,92,

%U 94,96,100,100,102,104,108,108,110,112

%N Maximum number of straight lines required to draw the boundary of any polyomino with n squares.

%C For n >= 7, polyominoes can have holes whose boundaries are also included.

%C An n-omino in the shape of a "staircase" has 2n boundary edges, so a(n) >= 2n.

%C If we "join" copies of the X pentomino (sharing one square) then we can do better than the above lower bound. This gives us a(4k+1) >= 8k+4, for any k >= 0.

%C It appears that a(n) = 2*n+2 for n (mod 4) == 1, otherwise a(n) = 2*n, which coincides with the lower bounds above. - _Lars Blomberg_, Nov 09 2017

%C The conjecture that a(n) = 2*n+2 for n (mod 4) == 1, otherwise a(n) = 2*n, is proven. See link. - _John Mason_, Jun 08 2021

%H John Mason, <a href="/A282939/a282939.pdf">Proof of conjecture</a>

%e For n=1, we have the monomino (single square), so a(1)=4.

%e For n=2, we have the domino, so a(2)=4.

%e For n=3, we have the L tromino, so a(3)=6.

%e For n=4, we have the T and S tetrominoes, so a(4)=8.

%e For n=5, we have the X pentomino, so a(5)=12.

%K nonn

%O 0,2

%A _Dmitry Kamenetsky_, Feb 25 2017

%E a(7)-a(19) from _Lars Blomberg_, Nov 09 2017