Cómo probar que coloreando cada punto con$1$% de$n$ colores para el$n$% específico crea un triángulo isósceles-derecho

Question

Para los números naturales$n>1$, siempre puede encontrar$3$ puntos del mismo color formando un triángulo rectángulo isósceles en cualquier color de$\mathbb Z^2$ con$n$ colores.

Este problema me fue dado y como no tengo idea de por dónde empezar, agradecería algo de ayuda.

Answer 1

No estoy seguro si es una exageración, pero Gallai la extensión de van der Waerden del teorema dice que para cualquier finito para colorear de $\mathbb{Z}^2$, existe un color que ha arbitrariamente grande de la plaza de sub-matrices. De ello se deduce que para cualquier finito para colorear de $\mathbb{Z}^2$, siempre se puede encontrar un mono de color isoceles derecho-triángulo. Usted puede encontrar una primaria de la prueba en el caso de 2 y 3 colores aquí. Usted puede encontrar los mejores resultados para los triángulos en $n\times n$ cuadrículas en Monocromático Equilátero Derecho Triángulos en el Entero de Rejilla - Graham, et al. al..

Answer 2

Vamos a dar primero el argumento para mostrar un monocromático en ángulo recto triángulo isósceles (MCRIT) existen dos colores y, a continuación, mostrar que el argumento se generaliza para cualquier número finito de colores.

Considere la posibilidad de la primera fila, no debe existir $3$ puntos que son equidistantes entre sí; esto es equivalente a encontrar un monocromático arithemetic la progresión de la en $[n]$. (Dejamos al lector a convencerse de que dos coloración de $[7]$ contendrá una secuencia.)

INSERTAR FIGURA

Considere la figura anterior; Puntos de $1$ & $2$ son del mismo color así que apunte $4$ tendrá que ser el otro de color con el fin de evitar un MCRIT. Asimismo, los puntos de $2$ & $3$ el punto promedio $5$ es el otro color y puntos $1$ & $3$ el punto promedio $6$ es el otro color; pero ahora los puntos $4$,$5$ & $6$ se forma un MCRIT y por lo tanto el resultado se muestra de dos colores.

Para mostrar el resultado de $c$ colores necesitamos un corolario de van der Waerden del Teorema, ver teorema del $(2.1)$ & $(2.10)$ aquí http://u.cs.biu.ac.il/~tsaban/RT/Book/Chapter5.pdfhttp://u.cs.biu.ac.il/~tsaban/RT/Book/Chapter5.pdf

Deje $N(n,c)$ denotar la longitud mínima de una $c$-color de la secuencia de un monocromático de larga duración $n$ a existir.

En la primera $N(N( \cdots N(N(3,2),3) \cdots,c-1),c)$ elementos de la primera fila, existe una secuencia de un monocromático secuencia de puntos equidistantes de la longitud de la $N( N( \cdots N(N(3,2),3) \cdots,c-2,c-1)$. Ahora, considere el "triángulo" de puntos por encima de estos, se debe evitar el color de la primera de color con el fin de evitar un MCRIT. La repetición de esta unido de forma inductiva nos va a llevar el caso de dos colores en $N(3,2)=7$.