Las diagonales dibujadas dividen el tablero$N\times N$ en regiones$K$. Para cada$N$, determine los valores más pequeños y más grandes posibles de$K$.

Question

Deje $N$ ser un entero positivo. En cada una de las $N^2$ unidad de plazas de un $N\times N$ junta, una de las dos diagonales es dibujado. El dibujado de las diagonales dividir el $N\times N$ junta en $K$ regiones. Para cada una de las $N$, determinar el más pequeño y el más grande de los posibles valores de $K$.

Así que, me las arreglo para encontrar el valor más pequeño que se $2N$ y puede ser realizado con el dibujo de todos los de la diagonal paralela a la otra. Por qué no puede ser más pequeño?

Podemos observar esta configuración como un plano gráfico con $2N$ horizontal y $2N$ bordes verticales en el borde de la tabla y $N^2$ bordes en diagonal, por lo que hemos total $E=4N+N^2$ bordes. También este gráfico ha $4N$ vértices en el borde de la mesa y algunos, decir $r$ vértices en el interior de la tabla, por lo que tenemos $V = 4N+r$ vértices. Claramente $r\leq (N-1)^2$. Estamos interesados en el número de limitada caras de este gráfico. Desde este gráfico no es necesario conectados tenemos que utilizar la fórmula de Euler $$V-E+F = c+1$$ where $c$ is a number of a connected components. Since $c \geq 1$ el número \begin{eqnarray}K &=& F-1\\&=& E-V+c\\ &\geq& (4N+N^2)-(4N+r)+1\\ &\geq& N^2-(N-1)^2+1\\ &=& 2N\end{eqnarray}

Ahora me gustaría saber también el mayor valor utilizando la fórmula de Euler , pero no puedo encontrar fácil una estimación de $c$ que iba a hacer. Alguna idea?

De todos modos, la respuesta es $K_{\max} = \Big[{(N+1)^2 +1\over 2}\Big]$

Answer 1

Cada una de las $4N$ a los bordes exteriores es un lado de exactamente una cara y todos los demás de en la mayoría de los dos. De modo que la suma de los tamaños de las caras es igual en la mayoría de las $2N^2+4N$. Ahora, cada cara tiene que ser de al menos cuadrilátero excepto esquina caras que pueden ser triángulos, pero no son en la mayoría de las $4$ de ellos tomando en la mayoría de las $12$ de $2N^2+4N$. Así que en total no puede haber más de: $$\frac{2N^2+4N-12}{4}$$ No de caras triangulares y, por tanto, en la mayoría de los $$\frac{2N^2+4N-12}{4}+4=\frac{(N+1)^2+1}{2}$$ Caras en total. La igualdad se consigue si para cada diagonal se direcciones alternas.

Usted también no tiene que utilizar la fórmula de Euler con el fin de demostrar que hay al menos $2N$ lados. Imagina que estas diagonales son en realidad los espejos y las que emiten la luz desde el punto medio de cada borde externo en la dirección perpendicular a ella (en la plaza del interior). Es fácil ver que tal haz de luz no puede terminar en un bucle, así que tiene que terminar de entrar en otro borde externo. También, dado que tales camino uno puede reconstruir fácilmente la colocación de los espejos y por lo tanto el límite de la región de que el rayo viaja a través de. De ello se desprende que cada región ha $0$ o $2$ bordes externos y por lo tanto en la mayoría de los dos así que hay al menos $2N$ regiones.