Olimpiada Matemática Española 2011 – Problema 1: Segmentos de un polígono regular y colores

El pasado fin de semana se ha celebrado en Pamplona la XLVII Edición de la Olimpiada Matemática Española. Y aprovechando este evento vamos a hacer lo mismo que hicimos con la IMO 2008: vamos a plantear en Gaussianos los seis problemas de la OME durante las próximas semanas.

Comenzamos hoy con el primer problema. Su enunciado es el siguiente:

En un polígono regular de 67 lados trazamos todos los segmentos que unen dos vértices, incluidos los lados del polígono. Elegimos n de estos segmentos y asignamos a cada uno de ellos un color entre 10 colores posibles. Halla el valor mínimo de n que garantiza que, independientemente de cuáles sean los n segmentos elegidos y de cómo se haga la asignación de colores, siempre habrá un vértice del polígono que pertenece a 7 segmentos del mismo color.

Tened en cuenta que estos problemas se proponen a alumnos de Bachillerato, por lo que no deben ser demasiado difíciles…¿o sí?

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

9 Comentarios

  1. Un vértice (al menos) debe tener 7 aristas del mismo color, luego todos los vértices deben tener (al menos) 6 aristas del mismo color (principio del palomar).

    Dicho de otro modo, el número mínimo de aristas con un mismo color (para cumplir el enunciado) deben ser 67 * 6 / 2 + 1 = 202.

    Ahora, tenemos 10 colores posibles (y otra vez por el principio del palomar) para asegurar que al menos un color es usado en 202 aristas, éstas deben ser 202 * 9 + 1 = 1819.

    Digo…

    Publica una respuesta
  2. A mí me salen 2011…

    Veamos, por el Principio del Palomar, necesitaría poder asegurar que de algún vértice salen 61 aristas para poder asegurar que hay, al menos, siete de ellas con el mismo color (pues el caso más desfavorable, para tal vértice, sería que hubiera 6 aristas de cada uno de los 10 colores, es decir, 60 aristas).

    Ahora, si el número de aristas es (60×67)/2 + 1 = 2011, es seguro que de alguno de los vértices salen 61 aristas (de nuevo por el Principio del Palomar, el caso más desfavorable sería que de cada vértice salieran exactamente 60 aristas, caso en el que habría (60×67)/2 aristas en total).

    Así, está probado que tomando n=2011 segmentos, se cumple la condición del enunciado. Ahora, para probar que éste es el mínimo valor posible de n, veamos que existe una forma de colocar 2010 aristas de modo que no se cumple la condición del enunciado (evidentemente, para n < 2010, bastaría con suprimir algunas de éstas).

    (Lo que queda lo pongo en otro comentario, que no cabe)

    Publica una respuesta
  3. Llamemos a1,a2,…,a10 a los 10 colores de los que disponemos.

    En primer lugar, definimos una distancia entre vértices V,V’ del polígono del siguiente modo:

    d(V,V’) = (número de vértices mínimo por los que hay que pasar para, andando por lados del polígono, llegar de V a V’) – 1

    Así, d(V,V)=0 para todo V; d(V,V’) = 1 si VV’ es un lado del polígono, etc.

    Ahora, para cada vértice V, trazamos todas las aristas VV’ de manera que se cumpla d(V,V’)>3 (es decir, para cada vértice, estamos trazando 60 aristas, para un total de 2010 aristas). Hecho esto, para cada una de tales aristas VV’, definimos su color del siguiente modo:

    – Si 4<=d(V,V') <=6, el color es a1.
    – Si 7<=d(V,V')<=10, el color es a2.

    Y así sucesivamente. Esta configuración del polígono satisface que, de cada uno de los vértices salen exactamente 6 aristas de cada color.

    Publica una respuesta
  4. De acuerdo con al solución de piteryon.
    Además habiendo sido un participante de estas cosas no me resulta nada extraño que la solución sea exactamente 2011.

    Publica una respuesta
  5. Hola, perdón… sé que esto no tiene nada que ver con ese problema pero quiero que me presten atención solo un momento…

    ¿Como averiguo la forma de demostrar que algo se puede hacer con lapiz y compaz? Esque me topé con una pregunta… es posible dibujar un triángulo conociendo la dimención de la altura, mediana y bisectriz de diferentes vértices??

    Quisiera saber cómo sé que se puede o no… es posible hacerlo con lapiz y compaz? y cómo se demuestran esas cosas?… gracias…

    Publica una respuesta
  6. Como participante de estas olimpiadas, debo decir que no hay nada mejor que estar resolviendo un problema y ver que la solución coincide con el año. Es casi una garantía de que está bien.

    Publica una respuesta
  7. Si un vértice tiene 7 segmentos del mismo color hemos acabado. Suponemos entonces que tiene a lo sumo 6 de cada uno, o sea, a lo sumo tiene 60 sin que haya 7 iguales. Contándolos en todos los vértices hacen un total de \frac{67\cdot60}{2}=2010. Por lo tanto si se escoge n=2010+1 por el principio del palomar hemos acabado. Sé que más de uno lo habrá puesto ya pero me apetecía decirlo.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: El pasado fin de semana se ha celebrado en Pamplona la XLVII Edición de…
  2. Los problemas son divertidos | cornisa.net - [...] Los problemas son divertidos var addthis_product = 'wpp-254'; var addthis_config = {"data_track_clickback":true};A través de Gaussianos, me he podido…
  3. Los problemas de la Olimpiada « La aventura de las matemáticas - [...] Problema 1 [...]

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *