|
%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
| 