Puntos de la cuadrícula de coloración con dos colores

Question

Deje $S$ ser un conjunto finito de muchos de los puntos de cuadrícula (puntos en el sistema de coordenadas con coordenadas enteras).

Es siempre posible a color con dos colores, rojo y azul, de tal manera que en cada vertical y horizontal de la línea de las siguientes afirmaciones es verdadera:

si hay $R$ cantidad de glóbulos rojos y $B$ número de puntos azules, de $|R-B|\leq 1$?

Esta es una manera más fácil olimpiada de combinatoria problema (desde 1980), pero todavía no puedo resolver. Traté de encontrar estrategias de los colores, pero ahora no estoy seguro de que la afirmación es verdadera.

Answer 1

Deje $C$ ser la condición de una línea (fila o columna) que el número de puntos rojos difiere el número de puntos azules a la mayoría de los $1$.

Vamos a probar la declaración por inducción sobre el número de puntos de cuadrícula $n=|S|$. Supongamos que todos los conjuntos con un número de puntos de cuadrícula $<n$ puede ser teñido con el rojo y el azul de los puntos tales que en cada fila y columna, $C$ está satisfecho. Vamos a probar ahora a la declaración de la $n$ puntos de cuadrícula.

Caso 1: Hay al menos una fila o columna con un número impar de elementos

Llame a dicha fila/columna $L$. En este caso podemos elegir cualquier punto de $P$ de $L$ y aplicar nuestra hipótesis de inducción en $S- \{P\}$, para obtener una coloración de $S- \{P\}$. El número de puntos en $L- \{P\}$ es aún, y por lo tanto debe contener igual número de Rojo y Azul puntos si es para satisfacer la condición de $C$. Por lo tanto, si hemos de color P azul o rojo, la condición de $C$ todavía está satisfecho por $L$. Deje $L_2$ ser la línea a través de $P$ perpendicular a $L$. Hemos color P rojo si el número de puntos azules en el $L_2- \{P\}\geq$ número de puntos rojos en $L_2- \{P\}$ y azul de otra manera. Esta coloración de $S$ satisface $C$ para todas las filas y columnas, y hemos terminado.

Caso 2: Todas las filas y columnas tienen un número par de elementos

Este caso es más complicado.

Elija cualquier punto de $P_1$ y dibujar una línea horizontal a través de ella se extiende hacia la derecha o a la izquierda (lo que jamás lado tiene al menos $1$ punto). Deje $P_2$ ser el primer punto se cumple. $P_2$ debe existir como todas las filas y columnas tienen un número par de elementos. Ahora dibuje una línea vertical a través de $P_2$, que se extiende hacia arriba o hacia abajo (lo que lado tiene al menos $1$ punto), y deje $P_3$ ser el primer punto se cumple. Dibuje una línea horizontal a través de $P_3$ y así sucesivamente. Deje $j$ ser el menor número tal que $P_j=P_i$ para algunos $i<j$.($j=11$ en la figura) Si $i$ e $j$ tienen la misma paridad(para $i=3$ en la figura), $P_iP_{i+1}$ e $P_{j-1}P_{i}$ son perpendiculares. Si no (si por ejemplo, $i=2$ en la figura), el incremento de $i$ por 1. Entonces, para el nuevo $i$, $P_iP_{i+1}$ e $P_{j-1}P_{i}$ son perpendiculares.

Aquí está un diagrama de la ilustración.

Deje $S'=\{P_i,P_{i+1},...,P_{j-1}\}$. Podemos aplicar la hipótesis de inducción en $S-S'$ y color $P_i$ azul, $P_{i+1}$ rojo, $P_{i+2}$ azul y así sucesivamente hasta $P_{j-1}$ es de color Rojo.

Cualquier línea en S pasa a través de un número de pares de puntos adyacentes de S' con diferentes colores, y a través de los puntos de $S-S'$ y por lo tanto satisface $C$. Por lo tanto, hemos terminado.

(El caso base es trivial y se deja como ejercicio.)

$\blacksquare$