Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Supongamos que a ningún vértice llegan $7$ segmentos del mismo color. Entonces, a cada vértice llegan a lo sumo $6$ segmentos de cada uno de los $10$ colores, es decir, un máximo de $60$ segmentos. Esto nos da un total como máximo de $\frac{60\cdot 67}{2}=2010$ segmentos (dividimos por dos ya que estamos contando cada segmento dos veces, una por cada uno de sus extremos). De esta forma, si tuviéramos $2011$ (¡el año!) o más segmentos, siempre habrá un vértice que pertenece a $7$ segmentos del mismo color.

Veremos ahora que hay una forma de escoger $2010$ segmentos y colorearlos de forma que a cada vértice llegan exactamente $6$ segmentos del mismo color, lo que demuestra que el mínimo que nos pide el enunciado es efectivamente $2011$. Numeramos los vértices consecutivamente del $1$ al $67$ y consideramos los $2010$ segmentos que unen cada vértice $n$ con el vértice $n+k$, siendo $0\lt|k|\leq 30$ un entero, donde además consideramos los números asignados módulo $67$. Ahora bien, dado el segmento que une $n$ con $n+k$, lo pintamos del primer color si $0\lt|k|\leq 3$, del segundo color $3\lt |k|\leq 6$, del tercer color si $6\lt|k|\leq 9$ y así sucesivamente hasta el décimo color en el que tomamos $27\lt |k|\leq 30$. Al haber tomado el valor absoluto, esta coloración es consistente, en el sentido de que si el segmento que une $n$ y $n+k$ está pintado de un color, el segmento que une $n+k$ y $n=(n+k)-k$ también se pinta del mismo color. De esta forma, cada vértice está unido a exactamente $6$ con segmentos de cada uno de los $10$ colores (observemos también que cada $n$ no está unido ni a $n\pm 31$ ni a $n\pm 32$ ni a $n\pm 33$).