A383420 Maximum (equal) number of red and blue tiles on an n X n matrix, where opposite colors cannot be adjacent diagonally or edgewise, and where a cluster of the same color can be no greater than n.

0, 0, 6, 8, 16, 24, 30, 38

Offset: 1

Author

Jakub Buczak, Apr 26 2025

Keywords

• nonn
• hard
• more

Comments

a(n) refers to the total number of both red and blue tiles covering the n X n matrix, and thus all the terms are even.

Examples

			a(2) = 0, since red and blue tiles, regardless of the arrangement will always either border sideways or diagonally.
a(3) = 6, a simple example could be:
  [R R R]
  [     ]
  [B B B]
		

Links

• Jakub Buczak, Optimal matrix example with a(n) tiles for each n
• Jakub Buczak, All 105 arrangements for n=4 with 8 tiles ignoring rotation, mirroring and color swapping.

Crossrefs

Cf. A000290, A002378, A023365, A001105, A033587.

Formula

The lower and upper bounds apply to all n > 3.

k is the root of the smallest square greater than n, b = ceiling((n+1)/(k+1)). The variable x is defined as 5*((n+1)/(k+1) - b), if (n+1)/(k+1) - b > 0, otherwise x=0.

a(n) <= (b*k)^2 + n^2 - (n - x)^2 for all n.

a(n) => n^2/2, for n == 0 mod 4.

a(n) => (n^2 + n - 2)/2, for n == 1 mod 4.

a(n) => n^2/2 + n - 4, for n == 2 mod 4.

a(n) => (n^2 + n - 4)/2, for n == 3 mod 4.