Los estudiantes que ver las orejas de otro estudiante

Question

Un estudiante está de pie en cada celda de una $n\times n$ cuadrícula, mirando a una de las cuatro direcciones: arriba, abajo, izquierda, derecha. Resulta que ningún estudiante se encuentra en la frontera y en busca de la rejilla, y ningún estudiante directamente ve la cara de otro estudiante (cada alumno se ve bien en el oído o en la parte posterior de otro estudiante). ¿Cuál es el mínimo número de estudiante que ve la oreja?

Creo que podemos lograr $n+4$ con esta configuración, se muestra para $n=5$. (Las flechas muestran de qué manera los estudiantes se enfrentan.)

$$\begin{matrix} \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\rightarrow&\downarrow\\ \rightarrow&\rightarrow&\rightarrow&\uparrow&\leftarrow \end{de la matriz}$$

Answer 1

El mínimo es de $n+2$, con la construcción en chubakueno del comentario.

La prueba de que esta es mínima:

Dividir a los alumnos en las líneas (máximo subconjuntos de los estudiantes en línea recta, todos mirando en la misma dirección).

El último estudiante en cada línea debe estar buscando en una oreja (de hecho, el número de líneas es igual al número de estudiantes que buscan en una oreja).

Cada línea tiene en la mayoría de las $n-1$ de los estudiantes.

Por lo tanto, hay por lo menos $\lceil \frac{n^2}{n-1} \rceil = n+2$ líneas, y así por lo menos esto muchos estudiantes que buscan en un oído.

Una ilustración (ligera modificación de chubakueno del comentario):

$$\begin{matrix} \downarrow&\downarrow&\downarrow&\downarrow&\leftarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\uparrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\uparrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\uparrow\\ \rightarrow&\rightarrow&\rightarrow&\rightarrow&\uparrow \end{de la matriz}$$

Usted ve $n+1$ líneas, cada una con el máximo de $n-1$ elementos, además de un solitario estudiante en una línea de un elemento (parte superior derecha).

Answer 2

Considere la posibilidad de una ligera modificación del arreglo: $$\begin{matrix} \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\ \downarrow&\downarrow&\downarrow&\downarrow&\color{red}\downarrow\\ \color{red}\downarrow&\color{red}\downarrow&\color{red}\downarrow&\color{red}\downarrow&\color{red}\leftarrow\\ \rightarrow&\rightarrow&\rightarrow&\color{red}\rightarrow&\color{red}\uparrow \end{de la matriz}$$ que se ve mejor para mí, y en el caso general, da $n+3$ el número de estudiantes que ver el lado de otro estudiante de la cara por $n \ge 3$, y para $n = 2$, el mínimo es obviamente $4$.