Cuando leí una pregunta en este foro Maximizar el primer sumas de dinero en una mesa, me di cuenta de que cuando $9$ enteros consecutivos son para ser insertado en un $3\times3$ cuadrícula, no importa lo que los números enteros se disponen en, debe haber al menos una suma de $3$ números, ya sea horizontal, vertical o diagonal que puede ser divisible por $3$. Estoy interesado en encontrar una prueba, pero lo que he conseguido es simplificar el $9$ enteros para convertirse en {$0$, $0$, $0$, $1$, $1$, $1$, $2$, $2$, $2$} (es decir, tomando el $\mod 3$ resultados de la $9$ números enteros consecutivos) y, a continuación, tratar de ellos por la fuerza bruta. Sin duda, este método no da una buena prueba. Hay alguna mejor manera de demostrarlo?
Respuesta
¿Demasiados anuncios?
El trabajo de más de $\mathbb{Z}_3$ es una buena idea. Sospecho que hay es un elegante hotel de pigeon-hole principio argumento al acecho alrededor, pero aquí es otro.
Observe que las entradas en cualquier línea (= fila/columna/diagonal) de sumas a cero (modulo $3$) si y sólo si todas las entradas son iguales ni todos son diferentes. Así que supongamos que tenemos una matriz de $M$ ( $\mathbb{Z}_3$ ), tales que cada línea tiene exactamente dos entradas son iguales.
Vamos a dibujar un gráfico bipartito $G$ con desdoblamiento $(L,R)$ cuando la $8$ vértices de $L$ representan el $8$ diferentes líneas y $R=\{0,1,2\}$. Unirse a un vértice $\ell\in L$ e una $x\in R$ si $x$ es una entrada en la línea de $\ell$.
Por nuestra suposición sobre la $M$, cada vértice $L$ tiene el grado exactamente $2$, y por lo tanto $G$ tiene exactamente $16$ bordes.
Por otro lado, echemos un vistazo a los grados de los tres vértices en $R$.
Reclamo: Cada vértice $x\in R$ tiene un grado mínimo de $5$.
Prueba: Si $(i,j),(k,l),(m,n)$) son las coordenadas de la $x$'s $M$, entonces al menos dos de los índices de fila son distintos y al menos dos de los índices de columna son distintos. Esto le da al menos $4$ líneas (todas en filas o columnas). Pero si el conjunto de índices de fila, o el conjunto de la columna de los vértices son distintos, entonces tenemos $5$ líneas. Por otro lado, si dos de la fila índices son iguales y dos de los índices de columna son iguales, entonces no es una diagonal que contiene $x$, y así un $5$th línea.
Desde cada vértice $R$ tiene un grado mínimo de $5$, pero sólo hay $16$ bordes en $G$, debemos tener dos vértices en $R$ con grado de $5$, y uno de grado $6$.
Deje $x$ ser la entrada en el centro de la $M$. Esta entrada es en $4$ líneas, y así corresponde a $4$ bordes en $G$. Hay dos más $x$'s $M$.
Caso 1: una de la otra $x$'s está en una esquina de la entrada. a continuación, llegamos $2$ más de los bordes en la $G$ a partir de estas dos líneas (la correspondiente fila y columna). Así que el grado de $x$ al menos $6$. Dado que el grado no puede ser mayor que $6$, el final de la $x$ sólo puede estar en una de dos posiciones. Rotación/reflexionar si es necesario, esto significa que $M$ parece: $$M=\begin{bmatrix} x & x & \cdot \\ \cdot & x & \cdot\\ \cdot & \cdot & \cdot\end{bmatrix}.$$ Let $y$ be the entry in coordinates $(1,3)$. This forces $M$ to look like: $$M=\begin{bmatrix} x & x & y \\ y & x & \cdot\\ y & \cdot & \cdot\end{bmatrix}.$$
Pero luego se nos puede llenar la tercera entrada posible en una manera, la producción de una línea con distintas entradas: $$M=\begin{bmatrix} x & x & y \\ \color{red}{y} & \color{red}{x} & \color{red}{z}\\ y & z & z\end{bmatrix}.$$
Caso 2: Ninguna de la esquina entradas de $M$ igual $x$. Dado que no todos los tres $x$'s están en la misma línea, esto significa que (rotación si es necesario) $M$ parece: $$M=\begin{bmatrix} \cdot & x & \cdot \\ x & x & \cdot\\ \cdot & \cdot & \cdot\end{bmatrix}.$$
Deje $y$ ser la entrada en coordinar $(1,1)$. A continuación, $M$ sólo puede mirar como $$M=\begin{bmatrix} y & x & y \\ x & x & \cdot\\ y & \cdot & \cdot\end{bmatrix}.$$ But now we can fill in the $z$'s obtaining a line with distinct entries, a contradiction: $$M=\begin{bmatrix} \color{red}{y} & x & y \\ x & \color{red}{x} & z\\ y & z & \color{red}{z}\end{bmatrix}.$$
