Existe un límite superior de $\left\lfloor\frac23(N^2+N-1)\right\rfloor$ que es ajustado para ciertos valores de $N$ .
Si hay $B$ cuadrados negros, tienen $4B$ lados. De estos, restamos los que están a lo largo de los lados de la cuadrícula: hay como máximo $4N-1$ de estos (no $4N$ porque entonces obtendríamos un ciclo alrededor del límite de la cuadrícula). Como no hay ciclos, hay como máximo $2(B-1)$ lugares en los que dos cuadrados negros son adyacentes (es el número de aristas de un árbol).
Así que el resto de $\ge 4B - (4N-1) - 2(B-1) = 2B - 4N + 3$ Los lados corresponden a los límites entre un cuadrado negro y un cuadrado blanco.
Por otro lado, hay como máximo $4(N^2-B)-1$ tales límites, porque cada uno se encuentra con un lado de un cuadrado blanco (y al menos un cuadrado blanco toca el lado de la cuadrícula). Así que tenemos $$ 2B - 4N + 3 \le 4(N^2-B) - 1 $$ que podemos resolver para obtener $B \le \frac23(N^2+N-1)$ .
Puedo igualar este límite superior cuando $N \equiv 4 \pmod 6$ (en cuyo caso el límite con el suelo incluido es $\frac23(N^2+N-2)$ ). En ese caso, el $10 \times 10$ La construcción se generaliza a la repetición de los siguientes bloques de altura $6$ :
@ @ @ @ @ @ @ @ @ @ @@
@@@@@@@@@@@@@@@@@@@@ @
@ @ @ @ @ @ @ @ @ @ @@
@@ @ @ @ @ @ @ @ @ @ @
@ @@@@@@@@@@@@@@@@@@@@
@@ @ @ @ @ @ @ @ @ @ @
excepto eliminando la primera fila del bloque superior y la última fila del bloque inferior. (El patrón puede extenderse horizontalmente a cualquier longitud uniforme, incluyendo $N$ .)
Por supuesto, podríamos contar los cuadros negros manualmente, pero el hecho de que esta construcción tenga $\frac23(N^2+N-2)$ cuadrados negros también se deduce al pasar por la prueba anterior: esta construcción tendrá $2(B-2)$ límites de cuadrado negro a cuadrado negro, ya que hay $2$ componentes conectados, y del $4N$ lados de la rejilla, todos menos $2$ cuadrados negros en el borde. Esto nos permite resolver $B$ .
