IMO 2013 en Santa Marta (Colombia) – Problema nº 6

Sexto y último problema de la IMO 2013 celebrada en Colombia:

Sea n \geq 3 un número entero. Se considera una circunferencia en la que se han marcado n+1 puntos igualmente espaciados. Cada punto se etiqueta con uno de los números 0,1, \ldots ,n de manera que cada número se usa exactamente una vez. Dos distribuciones de etiquetas se consideran la misma si una se puede obtener de la otra por una rotación de la circunferencia.

Una distribución de etiquetas se llama bonita si, para cualesquira cuatro etiquetas a < b < c < d con a+d=b+c, la cuerda que une los puntos etiquetados a y d no corta a la cuerta que los puntos etiquetados b y c.

Sea M el número de distribuciones bonitas y N el número de pares ordenados (x,y) de enteros positivos tales que x+y \leq n y mcd(x,y)=1. Demostrar que

M=N+1

A por él.

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.

7 Comentarios

  1. Problema difícil… diría que semejante al número dos de esta misma OIM pero bastante enrevesado.

    Publica una respuesta
  2. De los 700 participantes solo 15 personas aprox obtuvieron cierto puntaje en dicho problea y solo 7 lo resolvieron correctamente haciendo 7 puntos.

    1 Bielorrusia
    2 Canada
    2 Korea
    2 EEUU

    Sin lugar a dudas este fue el problema mas dificil de la IMO

    Publica una respuesta
  3. Eso parece, porque por aquí no hay ni siquiera un comentario que dé alguna idea sobre cómo resolverlo. A ver si alguien se anima.

    Publica una respuesta
  4. Algunas ideas.
    Empezamos por examinar el caso n=3. Ponemos todas las posibilidades. Siempre hay una que es la de los números ordenados de 0 a n. Como M = N +1 se me ocurre que tal vez excepto la distribución ordenada, para cada par x,y existe una ordenación. Hay que encontrar la relación entre ambos. Otra cosa se me ocurrió por inducción. Si añadimos el n+1 para cada distribución bonita solo hay unos lugares en el que intercalar este número. Pueden ser 1 o 2. Se trata de relacionar esto con los nuevos pares x,y que añade el considerar n+1. Solo son ideas. No alcancé nada útil, aunque creo que puede ir por ahí

    Publica una respuesta
  5. El problema es muy enrevesado, así que voy a explicarlo primero con un ejemplo y después indico cómo demostrarlo.

    Escribo las distribuciones empezando siempre por 0, ya que cualquier otra distribución se reduce a una de éstas por rotación.

    En una distribución bonita los números están agrupados en progresiones aritméticas crecientes, con diferencia el primer elemento (sin contar el 0).

    Por ejemplo, en la distribución bonita

    0-5-10-15-3-8-13-18-1-6-11-16-4-9-14-19-2-7-12-17

    están primero los múltiplos de 5 en orden creciente, después otro grupo que empieza con el 3 y va aumentando de 5 en 5 hasta el 18, luego el grupo del 1, y así.

    Esto siempre es así porque a la hora de añadir un nuevo elemento, la única posición posible es en la que le corresponde según este esquema. En el ejemplo, el siguiente elemento, que es el 20, tiene que ir entre el 15 y el 3.

    La única excepción es cuando el nuevo elemento es justo la suma de los dos extremos. En ese caso se puede añadir en cualquiera de los dos extremos (nuevamente, sin contar el 0). En el ejemplo esto pasará cuando toque añadir el 22.

    Entonces, para n, habrá una distribución por cada una para n-1, más una más por cada una para n-1 cuyos extremos sumen n. Hay exactamente una distribución de éstas por cada entero menor que n coprimo con n. Es fácil ver que N aumenta de la misma forma y por tanto, como la expresión que nos piden (M=N+1) se cumple para n=3, se cumple para cualquier n.

    Queda demostrar lo siguiente:

    – Todas las distribuciones bonitas para n provienen de distribuciones bonitas para n-1. Yo creo que esto es evidente, ya que si no la distribución no podría cumplir las condiciones en las que no interviene n.

    – La única posición posible para añadir un nuevo elemento es la que cumple este esquema. Esto es así porque los dos miembros de cada pareja que sume n tienen que quedar al mismo lado.

    – Añadiendo el nuevo elemento en esa posición la distribución sigue siendo bonita. Es fácil ver que si el nuevo elemento introduce alguna violación, tendría que haberla ya para los elementos anteriores.

    – Los dos extremos de una distribución bonita son coprimos entre sí. Esto se cumple para n=3 y se conserva, por la forma como se amplían las distribuciones. Sólo cambia un extremo cuando los dos extremos anteriores suman el nuevo elemento. Por tanto, si los extremos anteriores eran coprimos, el nuevo también lo será con cualquiera de ellos.

    – Para n-1, por cada entero menor que n coprimo con n, habrá una y sólo una distribución bonita cuyo primer elemento sea ese número y los dos extremos sumen n. Esa distribución sólo puede provenir del momento en que se añadió el mayor de los extremos. Como en ese momento ya se cumplía esta propiedad (se cumple para n=3) tenía que haber una y sólo una distribución, y por lo tanto la propiedad se sigue cumpliendo.

    Con esto queda demostrado.

    Siento haberme alargado tanto y no sé si se entiende muy bien, pero es que es complicado de explicar.

    Publica una respuesta
  6. No se entiende mucho, la verdad, golvano… 🙁

    Entiendo que sin dibujos o algun gráfico es muy difícil hacerse entender en este problema.

    Publica una respuesta
  7. En realidad, todo lo de la circunferencia y las cuerdas lo único que implica es que los números a, b, c y d tienen que estar intercalados.

    A partir de ahí, te puedes olvidar de todo eso y pensar sólo en secuencias de números.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Sexto y último problema de la IMO 2013 celebrada en Colombia: Sea un número…

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 *