Colorea una cuadrícula equilátera infinita con siete colores. ¿Es posible probar utilizando el principio de la casilla de verificación de que existe un triángulo monocromático?

Question

He encontrado un problema en Brillante, y pregunto si tiene una Caja de solución.

Usted tiene una red infinita de triángulos equiláteros y te gustaría llenar cada nodo con uno de los siete colores.

Hay alguna forma de hacer esto, por lo que ningún triángulo equilátero de cualquier tamaño formado por el entramado de líneas, sus tres vértices que comparten el mismo color?

Creo que puede ser una gran región que puede ser demostrado tener un triángulo equilátero.

He aquí un problema que utiliza una cuadrícula rectangular y demuestra que un rectángulo tiene de existir con todos los mismos vértices utilizando tres colores.

Que no se puede crear cualquier prueba, sin embargo. ¿Alguien puede mostrarme si (o si no) la afirmación anterior puede ser comprobado y cómo puede / ¿por qué no puede?

Nota: una solución que alguien contribuido incluye la inducción y Van der Waerden del teorema. Tal vez esa solución podría ser utilizado para encontrar la Caja enfoque?

Answer 1

No hay ninguna caja de la solución.

Podemos resolver el problema a través de la Ajtai-Szemerédi esquinas teorema. Las esquinas teorema no se trata de triángulos equiláteros en una malla triangular, pero acerca de los triángulos rectángulos de la forma $\{(x,y), (x,y+h), (x+h, y)\}$ en una cuadrícula rectangular; este es un insignificante modificación, ya que sólo puede sesgar la cuadrícula rectangular y a su vez estos triángulos rectángulos en los triángulos equiláteros que queremos. O para decirlo de otra manera, si tenemos el número de nodos en la red como en el diagrama de abajo, a continuación, las tripletas de la forma $\{(x,y), (x,y+h), (x+h, y)\}$ son precisamente los (vertical) triángulos equiláteros.

Las esquinas teorema es también una densidad resultado en lugar de un colorante resultado: se dice que para cualquier $\epsilon>0$, si tomamos $\epsilon N^2$ de $N^2$ puntos en un $N\times N$ rejilla, entonces podemos encontrar el triángulo entre los puntos que hemos seleccionado, siempre $N$ es lo suficientemente grande. Pero esto puede ser usado para obtener una coloración resultado: simplemente tome $\epsilon = \frac17$, escoja una lo suficientemente grande finito subgrid de su infinita red, y elegir el color más popular utilizado en los puntos en que subgrid.

Las esquinas teorema es bastante alta potencia resultado en la teoría de Ramsey. Pero afirman que no simple resultado de hacer el truco, porque el problema es al menos tan difícil como encontrar monocromática $3$plazo progresiones aritméticas, y usted puede ver los argumentos en el artículo de Wikipedia sobre van der Waerden del teorema de ver lo complicado de la prueba para las personas es incluso para $2$ o $3$ colores.

Suponga que tiene un $7$colorear de los enteros $1,2,\dots,n$, para algunos grandes $n$ sin $3$-término de una progresión aritmética. Luego, dando un punto de $(x,y)$ en la red el color de la entero $2x+y$, podemos el color de algunos de gran parte de la malla triangular; que la porción de la red no tendrá ningún monocromática de triángulos. Vertical triángulo tiene coordenadas $\{(x,y), (x,y+h), (x+h,y)\}$ que corresponde a los números enteros $2x+y, 2x+y+h, 2x+y+2h$. Un triángulo invertido tiene coordenadas $(x,y+h), (x+h,y), (x+h,y+h)$ que corresponde a los números enteros $2x+y+h, 2x+y+2h, 2x+y+3h$. De cualquier manera, se forma una $3$-término de una progresión aritmética.

Así que si usted encuentra una rápida encasillar solución aquí, usted tendría una rápida encasillar solución a la longitud-$3$ caso de van der Waerden del teorema, que sería un gran negocio!