Supongamos que tenemos el tablero de ajedrez de ${N}\times{N}$ tales que dos casillas son adyacentes si comparten un lado común. Rellenar todas las casillas con números enteros para que los números en las casillas adyacentes difieren por $1, 0$ o $-1$. Demostrar que un número aparezca al menos N veces.
Respuesta
¿Demasiados anuncios?
Para cualquier válido $n$ $n$ cuadrícula, vamos a considerar algunos de establecer $S_k$ que contiene cualquier celda cuyo valor es $\leq k$ para un determinado $k$. Si establecemos $k$ el valor máximo de las células (llaman a esto $m$) en toda la cuadrícula, a continuación, $S_k$ va a contener cada celda de la cuadrícula (este es nuestro caso base).
Podemos disminuir el $k$ a el menor valor posible para que $S_k$ todavía contiene al menos una celda de cada fila o cada columna. Esta condición tiene por $k=m$, y posiblemente tiene para algunos $k<m$, pero lo que importa es que este mínimo $k$ existe.
Después de encontrar este mínimo $k$, vamos a girar a la red que estamos viendo un escenario para que $S_k$ (al menos) contiene una celda de cada fila.
Vamos a centrarnos en una arbitraria de la fila. En esta línea, existe alguna celda con valor de $a$ tal que $a \leq k$ (esta celda sería en $S_k$, por definición), y también existe algún celular con valor de $b \geq k$ (desde $k$ es mínima a través de todas las filas y columnas).
Algo más de detalle en el $b$ celular: Desde $k$ es mínimo, sabemos que esto $b \geq k$ celular siempre existe. Supongamos que no, y que cada celda de la fila tenía valor $k-1$ lugar (es decir, algo $<k$). Entonces podríamos girar la rejilla y decir que cada fila (antes de la columna) contiene una celda con valor de $\leq k-1$, lo que contradice nuestra condición de que $k$ fue mínima, para empezar.
Las células adyacentes pueden sólo se diferencian en la mayoría de las $1$ en términos de magnitud absoluta, lo que significa que en cada fila hay una cierta contiguos / horizontal de la vía de $a$ $b$que debe finalmente encuentro un celular con valor de $k$.
Dado que esta condición es verdadera para todos los $n$ filas, vemos que $k$ debe ocurrir al menos $n$ veces.
