Color de todos los subconjuntos no vacíos de $[n] = \{1,2,\ldots,n\}$ $1,2,\ldots,r$ de colores. Muestran que, para todos grande $n$, existen dos subconjuntos no vacíos disjuntos $A,B \subseteq [n]$ tal que $A$, $B$, y $A \cup B$ todos tienen el mismo color.
Respuestas
¿Demasiados anuncios?
Shabaz
Puntos
403
Para dos colores, sea $n$ $9$. Tiene que haber cinco solteros del mismo color. Que sea rojo. Ahora para que esto falla, todos los pares de estos deben ser azules. Entonces los cuatro conjuntos de elementos son de color rojos, todos los conjuntos de tres elementos son de color azules. Entonces el conjunto de los cinco debe coincidir con un par de sus subconjuntos. ¿Puedes ver cómo extender esto a $r$ colores?
Kyle Rogers
Puntos
116
De dos colores, vamos a $n$$5$. Considere el grafo completo sobre el conjunto de vértices $\{0,1,2,3,4,5\}$. El Color de los bordes de esta $K_6$, dando el borde de la $uv\ (0\le u\lt v\le5$) el color del set $\{u+1,u+2,\dots,v\}$. Un monocromático triángulo le dará dos disjuntos no vacíos conjuntos de $A,B$ y su unión a $A\cup B$ todos de un mismo color. A ver que $n=5$ es el mejor posible para $r=2$, el color de los subconjuntos no vacíos de a $[4]$ coloreando $1$-conjuntos y $4$-conjuntos de rojo, $2$-conjuntos y $3$-conjuntos de azul.
Para $r$ colores un argumento similar muestra que $n=\lfloor r!e\rfloor$ obras, pero en general esta no es la mejor posible.
