Al menos un triángulo monocromático de$p_n=\lfloor{en!}\rfloor+1$ puntos

Question

En el espacio se dan$p_n=\lfloor{en!}\rfloor+1$ puntos. Cada par de puntos está conectado por una línea, y cada línea está coloreada por uno de los colores$n$. Demuestre que hay al menos un triángulo de los lados del mismo color.

No entiendo cómo contrarrestar el$e$ aquí. Por favor ayuda.

Sin embargo, sin embargo, hice una suposición ... ¿Es$p_n = R(\underbrace{3,3,\cdots,3}_{n \ times})$? Lo adiviné solo porque es válido para$n=2,3$.

NB:$R$ es el número de Ramsey.

Answer 1

Deje $f(n)$ ser el tamaño máximo de un grafo completo que puede tener sus bordes de color con $n$ colores sin triángulos.

Observe que $f(n+1)\leq (n+1)(f(n))+1$. Para ver esto de elegir un vértice arbitrario $v$ y considerar las conexiones con el resto de $f(n+1)-1$ vértices. Si tuviéramos $f(n+1)-1>(n+1)f(n)$, a continuación, por el pigeon-hole principio no sería un conjunto con $f(n)+1$ vértices que están conectados a $v$ por el mismo color, esto es una contradicción, porque los $f(n)+1$ vértices tendría que tener a todos sus conexiones con sólo el restante $n$ colores, y un triángulo estaría formado.

Tenemos $f(2)=5\leq \lfloor e2!\rfloor $.

Ahora podemos demostrar por inducción que $f(n)\leq\lfloor en!\rfloor$

Sólo tenemos que demostrar que $(n+1)\lfloor en!\rfloor+1\leq \lfloor e(n+1)!\rfloor$.

esto es equivalente a probar que $(n+1)\lfloor en!\rfloor<\lfloor e(n+1)!\rfloor=\lfloor en!(n+1)\rfloor$

Todo lo que tenemos que hacer es mostrar que la parte fraccionaria de $en!$ al menos $\frac{1}{n+1}$, pero la parte fraccionaria de $en!$ $\frac{1}{n+1}+\frac{1}{(n+1)(n+2)}+\frac{1}{(n+1)(n+2)(n+3)}\dots$