Número mínimo de plazas en $n × n$ junta

Question

Llegó a través de esta pregunta:

Considere la posibilidad de una $n × n$ tablero cuadrado, donde $n$ es un fijo hasta entero positivo. El tablero está dividido en $n^2$ unidad de plazas. Decimos que dos diferentes plazas en la junta son adyacentes si tienen un lado común.

$N$ unidad de plazas en la junta están marcados de tal forma que cada cuadrado (marcado o sin marcar) en la junta directiva es adyacente a al menos una marcada plaza. Determinar el menor valor posible de $N$.

He encontrado una cota superior de a $N = \frac {n^2}2$. Pero este es el menor valor posible de $N$? Si es así, ¿cómo puedo demostrarlo?

He incluido una ilustración de mi límite superior para $n=2$ $n=4$ por debajo.

Editar

@jwsiegel ha vinculado a la supuesta solución aquí: http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln993.html

Se da la solución $$N = \frac{n(n+2)}{4}$$ No entiendo cómo esta solución es correcta. Las instrucciones para el marcado de plazas está dada como:

1. Color alternativo cuadrados en blanco y negro (como un tablero de ajedrez).
2. Busque primero en la longitud impar blanco de las diagonales. En todos los otros diagonal, marca alternativa de plazas (a partir de la frontera de cada momento, de modo que r+1 plazas están marcados en una longitud de la diagonal 2r+1).

Eso es todo. He seguido estas instrucciones (como yo los entiendo) por $n=4$ $n=6$ a continuación, utilizando una X para indicar una marcada cuadrado:

El número de plazas se ajusta a la solución dada, es decir,$N = 6$$n = 4$$N = 12$$n = 6$, pero NO marcado de la plaza adyacente a cualquier otro marcado plaza! Entonces, ¿cómo es esta una solución válida?

Solo puedo ver 3 posibilidades:

1. He marcado incorrectamente, o
2. La gente que hizo esta solución cuenta con un común esquina como secundarios comunes entre 2 plazas, o
3. La solución es incorrecta.

Por favor explique lo que me falta.

Answer 1

Considere la posibilidad de un infinito de tablero de ajedrez con cuadros marcados por los pares de números enteros y de la marca de cada cuadrado cuyos índices de satisfacer $$(i,j) \equiv (0,0) \pmod{4}$$ $$(i,j) \equiv (0,1) \pmod{4}$$ $$(i,j) \equiv (2,2) \pmod{4}$$ $$(i,j) \equiv (2,3) \pmod{4}$$ Esto proporciona un marcado el infinito de la junta con la propiedad deseada de tal manera que cada cuarta plaza está marcado. Así tenemos que $$\lim_{n\rightarrow \infty} \frac{N}{n^2} = \frac{1}{4}$$ que es claramente la mejor posible asintótica resultado.

De hecho, el valor de N es n(n+2)/4. La solución completa se puede encontrar aquí. http://www.cs.cornell.edu/~asdas/imo/imo/isoln/isoln993.html

Answer 2

jwsiegel ya ha dado tanto un asintótica respuesta a la pregunta original, y un enlace a una forma cerrada de la solución. Voy a abordar el Juan de la pregunta en los comentarios sobre jwsiegel la respuesta y Jens seguimiento de la pregunta en el post original.

En respuesta a Juan de la pregunta, "incluso Para n, esto es mejor, pero hace el trabajo, si n es impar?":

Nada en jwsiegel del asintótica resultado hace ninguna suposición sobre la paridad de $n$. Su respuesta proporciona una cobertura del infinito del plano que satisface las normas dadas en el post original. Cuando esta marca se limita a una $n \times n$ junta, se obtiene un marcado de la junta en la que todo el interior de la plaza se encuentra junto a una tabla marcada, con aproximadamente un cuarto de los cuadrados marcados con (exactamente 1/4 si $n$ es un múltiplo de 4). A continuación, la cubierta de la frontera, así, usted necesita agregar no más de $4(n-1)$ más de plazas. Al $n$ enfoques infinito, esta contribución es insignificante, por lo tanto obtenemos que, para $n$ grande, su cubierta de la junta directiva se requiere alrededor de una cuarta parte de las plazas para ser marcados. Ya que cada cuadrado es adyacente a la mayoría de los otros 4 plazas, se deduce que este resultado es asintóticamente óptimo.

Es, en principio, es posible calcular con precisión cuántas plazas están marcados por este procedimiento, pero no hay ninguna razón para esperar que va a ser el óptimo para cualquier fija $n$. Lo asintótico de la solución es proporcionar orientación para lo que de una forma cerrada de la solución debe satisfacer, es decir, que $$\lim_{n \to \infty} \frac{N}{n^2} = \frac{1}{4}.$$

Now, for OP's question. You forgot this part: "In every other such diagonal..." With that in mind, here are the cases you wrote up, corrected. Let the upper-left hand corner be white, as in your pictures. I've indicated the black squares using an ascii box; hopefully that should make it pretty clear.

$n=4$:

 X | ■ |   | ■ 
---------------
 ■ |   | ■ | X 
---------------
   | ■ |   | ■ 
---------------
 ■ | X | ■ |   

$n=6$:

 X | ■ |   | ■ | X | ■ 
-----------------------
 ■ |   | ■ |   | ■ |   
-----------------------
   | ■ | X | ■ |   | ■ 
-----------------------
 ■ |   | ■ |   | ■ | X 
-----------------------
 X | ■ |   | ■ |   | ■ 
-----------------------
 ■ |   | ■ | X | ■ |   

Observe that every black square is adjacent to exactly one marked white square. Now, as you observed, of course, no white square is adjacent to any marked square. But if we apply the exact same procedure to mark the black squares, then we obtain a marking of the entire board such that every square is adjacent to exactly one marked square. Then the claims are that (1) this board has $n(n+2)/4$ marked squares, and (2) this number of marked squares is optimal. Note that this closed form solution absolutely does depend on assuming that $$ n es par.

Answer 3

Usted puede producir los límites superiores para los tres casos $n \equiv 1,2,3 \mod{3} $.

En un $3n \times 3n$ plaza el límite superior es $3n^2$ debido a que se puede colorear cada tercera fila.

En el caso de que se trata de una $(3n+1) \times (3n+1)$ plaza, entonces el límite superior es $3n^2+ n + 2*\lceil \frac{(3n + 1)}{4} \rceil$. Este es el resultado de colorear cada tercera fila y la adición de un par cada dos incoloro espacios en la última fila.

Si es un $(3n+2) \times (3n+2)$ junta, el límite superior es $(3n+2)(n+1)$. Esto es lo que resulta de colorear cada tercera fila y la última fila.

Todos estos casos tienen el asintótica relación de cuadrados de colores para el total de plazas de $\frac{1}{3}$, pero también trabajar en cualquier finito de la junta con una proporción ligeramente superior.

Answer 4

Dado un cuadrado de tamaño de $n \times n$ donde $n \in \mathbb{Z^+} $, el valor más pequeño de casillas sombreadas $N$ puede ser determinado como uno de estos tres casos:

1. Si $n \equiv 3k \equiv 0 \mod 3$, $N = 3k^2$

2. Si $n \equiv 3k +1 \equiv 1 \mod 3$, $N= 3k^2 + k + 2*\lfloor\frac{3k+1}{4}\rfloor$

3. Si $n \equiv 3k +2 \equiv 2 \mod 3$, $N= (3k+2)(k+1)$