login
Maximum number of squares on an n X n chessboard such that no two are two steps apart horizontally or vertically.
0

%I #33 Dec 06 2022 09:59:39

%S 1,4,5,8,13,20,25,32,41,52

%N Maximum number of squares on an n X n chessboard such that no two are two steps apart horizontally or vertically.

%C The sequence 1, 4, 5, 8, 13, ... with g.f. -x*(1 +2*x -2*x^2 +2*x^3 +x^4)/ ((1+x) *(x^2+1) *(x-1)^3) and a(n)= 2*a(n-1) -a(n-2) +a(n-4) -2*a(n-5) +a(n-6) is a lower bound for a(n) achieved by packing 2x2 squares with 1's and 2x2 squares with 0's in a checkerboard pattern into the chessboard. - _R. J. Mathar_, Dec 03 2022

%F Conjectures:

%F a(n) = n^2/2 for n == 0 (mod 4).

%F a(n) = (n^2 + 1)/2 for n == 1 or 3 (mod 4).

%F a(n) = n^2/2 + 2 for n == 2 (mod 4).

%e For n = 1, a(1) = (1^2 + 1)/2 = 1

%e 1

%e For n = 2, a(2) = (2^2)/2 + 2 = 4

%e 11

%e 11

%e For n = 3, a(3) = (3^2 + 1)/2 = 5

%e Starting here the solutions are not unique. We can mix 2X2 blocks from and S shapes along the diagonals.

%e 110

%e 110

%e 001

%e or

%e 110

%e 011

%e 001

%e For n = 4, a(4) = (4^2)/2 = 8

%e 1100

%e 1100

%e 0011

%e 0011

%e or

%e 1100

%e 0110

%e 0011

%e 1001

%e For n = 5, a(5) = (5^2 + 1)/2 = 13

%e 11001

%e 11001

%e 00110

%e 00110

%e 11001

%e or

%e 11001

%e 01100

%e 00110

%e 10011

%e 11001

%e For n = 6, a(6) = (6^6)/2 + 2 = 20

%e 110011

%e 110011

%e 001100

%e 001100

%e 110011

%e 110011

%Y Cf. A048716.

%K nonn,more

%O 1,2

%A _Yang Hong_, Oct 20 2021