Teorema de Ramsey con sumas

Question

Recordemos que el teorema de Ramsey (infinito) dice que, si coloreamos a las parejas no ordenadas $\{n,m\}$ de números naturales con $n\neq m$ en dos colores distintos (si se quiere, piénsese en las aristas de un grafo completo en una cantidad numerable de vértices) siempre es posible encontrar un conjunto infinito $A$ tal que todos los pares $\{n,m\}$ con $n,m\in A$ tienen el mismo color (si se prefiere pensar en grafos, es posible hallar una cantidad infinita de vértices tal que el subgrafo generado por ellos es "monocromático". Aquí va un problema (no abierto, ni mucho menos) similar:

Supóngase que se colorean los números naturales en dos colores (es decir, a cada $n\in\mathbb N$ le asigno un color, rojo o azul, de manera totalmente arbitraria). Muestre que es posible encontrar dos números $n,m\in\mathbb N$ con el mismo color tales que $n+m$ también tiene el mismo color. (Ayudadita: es posible usar el teorema que menciono en el párrafo anterior).

Comments

Vamos, échenle ganas...

Answer 1

Veremos que podemos encontrarlos incluso en $\{1,2,3,4,5\}$. De estos cinco números hay tres del mismo color, digamos que es azul y que son $a<b<c$. Si $b-a$, $c-a$ ó $c-b$ son azules, entonces terminamos, pues alguna de las ternas $(a,b-a,b)$, $(a,c-a,c)$ ó $(b,c-b,c)$ funciona respectivamente. De otra forma, $b-a$, $c-a$ y $c-b$ son rojos, de modo que la terna $(b-a,c-b,c-a)$ funciona.

Esta prueba básicamente es una reformulación de la prueba para encontrar $\text{Ramsey}(3,3)$. Claro, también sale con el cañonazo del Teorema de Ramsey infinito, aplicándolo a la gráfica sobre los naturales tal que la arista $(i,j)$ se pinta de color $|i-j|$.

Comments

El cañonazo es el que tenía en mente, pero tienes razón, es mucho más sencillo que eso.

---

Acabo de venir a ver esta respuesta (para preparar una plática sobre teoremas de tipo Ramsey) y me di cuenta de un pequeño detalle: en tu segundo párrafo, al final, creo que en realidad la arista $(i,j)$ se pinta del mismo color que tiene el número $|i-j|$ (pero no "del color $|i-j|$", pues en tal caso estaríamos batallando con una infinidad de colores y el teorema de Ramsey falla).