IMO 2011 en Amsterdam – Problema nº 2

Hoy os traigo el segundo problema de la IMO 2011 celebrada en Amsterdam durante el mes de julio:

Sea S un conjunto finito de dos o más puntos del plano. En S no hay tres puntos colineales. Un remolino es un proceso que empieza con una recta l que pasa por un único punto P de S. Se rota l en el sentido de las manecillas del reloj con centro en P hasta que la recta encuentre por primera vez otro punto de S al cual llamaremos Q. Con Q como nuevo centro se sigue rotando la recta en el sentido de las manecillas del reloj hasta que la recta encuentre otro punto de S. Este proceso continúa indefinidamente.

Demostrar que se puede elegir un punto P de S y una recta l que pasa por P tales que el remolino que resulta usa cada punto de S como centro de rotación un número infinito de veces.

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.

22 Comentarios

  1. Por reducción al absurdo.

    Sea A= {x1,x2,..,xn} el conjunto de puntos no colineales sobre el plano y aceptemos la hipótesis de que no existen infinitas rotaciones de la recta L con eje de rotación establecido en algún xi de A.

    Partamos de x1, rotando L hasta topar con x2; desde x2 rotamos L hasta topar con x3; etcétera.

    Llegado a un xi, rotamos L y ésta, por definición, debería topar con un xk sobre el cuál volver a rotar y seguir el proceso. Pero he establecido como hipótesis que para ese cierto xi, L no sigue el proceso infinitamente, luego L no encuentra un punto de A sobre el cuál volver a rotar, por definición, lo cuál es imposible.

    Entonces la única alternativa que queda es que, llegados a cierto xi, la rotación de L llega a xk, pero dejando un punto xj que se encuentra en el segmento que une xi con xk. Pero entonces llegamos a la concluisón de que el segmento xi-xj-xk no cumple con la premisa de que los puntos de A no son colineales.

    Por lo tanto, cada xi€A ejerce como eje de rotación de L infinitamente.

    Publica una respuesta
  2. No sé si te he entendido muy bien Sebastian, mejor te pongo un ejemplo y me dices si tu demostración tiene en cuenta eso.

    Imagina que el conjunto está formado por cuatro puntos, tres de ellos están en los vértices de un triángulo equilátero imaginario, y el cuarto está en el centro de dicho triángulo.

    Si elegimos inicialmente un vértice cualquiera, y una recta que no “cruce” el triángulo, el remolino jamás pasará por el punto central, por lo que no cumpliría el enunciado.

    Es decir, que cualquier demostración que concluya que el enunciado es cierto para cualquier punto y recta iniciales, es errónea.

    Publica una respuesta
  3. Te entiendo perfectamente, Sive. Según lo que yo entiendo del enunciado, no hay una restricción que afirme que a partir del tercer vértice -el ejemplo que planteas- la recta L tenga que girar necesariamente hacia el primero, formando un bucle en el que, tal y como afirmas, jamás tocaría el punto central. Yo sobreentiendo que hay que demostrar que todo punto de S puede ser eje de rotación de forma infinita; según esto, afirmo -quizá de forma errónea- que, una vez llegada L al tercer vértice, puede rotar hacia el punto que se encuentra en el interior del triángulo y ahí seguir el proceso indefinidamente.

    De todos modos, me has hecho dudar. Por lo que sería interesante seguir estudiando el caso. Saludos.

    Publica una respuesta
  4. Efectivamente, Sive, el enunciado dice claramente que L rota hasta topar con el primer punto de S en su trayectoria. Por lo que te doy la razón (gracias por la aportación) y vuelvo a analizar el problema.

    Publica una respuesta
  5. El enunciado dice que CADA punto de S se usa como centro de rotación INFINITAS veces.

    Si el conjunto S está formado por uno, dos o tres puntos el enunciado es obviamente cierto.

    Si hay cuatro o más puntos en S, hay dos posibilidades:

    Si todos los puntos de S son vértices de un polígono convexo basta con elegir uno cualquiera de ellos como P y la recta l exterior al polígono (solo lo toca en P) para que se cumpla la demostración.

    Si los puntos de S no forman TODOS parte de un polígono convexo siempre habrá un conjunto de ellos que sí formen un polígono convexo que contenga en su interior a todos los restantes. Elijamos el punto y la recta que elijamos, en alguna de las rotaciones nos toparemos con un punto del polígono exterior. A partir de ahí la recta queda atrapada en un bucle perpetuo que rodea para siempre dicho polígono. Es decir, que los puntos interiores al mismo no volverán nunca a ser utilizados como centro de giro y por lo tanto estos interiores no se usarán INFINITAS veces como asegura el enunciado.

    Publica una respuesta
  6. Claro, JJG, eso es lo 1º que me pasó por la cabeza después del comentario de Sive. Todo contorno de un polígono convexo de ‘n’ vértices xk y aristas L valdría como resultado. Sin embargo, ¿será la única solución?

    Publica una respuesta
  7. Pero el último párrafo de JJGJJG es incorrecto. Puedo poner como ejemplo el triángulo equilatero con un punto en el centro de mi anterior comentario. Si se empieza en el punto central, y sin importar la recta que se elija, el remolino volverá infinitas veces al estado inicial.

    Es muy fácil demostrar, además, que esto sucede siempre, sin importar el punto y recta iniciales, ni la distribución de los puntos, el remolino volverá siempre al estado inicial, y lo hará infinitas veces.

    Sólo hay que notar que el remolino es reversible. Podemos girar la recta en sentido antihorario, y volver sobre nuestros pasos.

    Esto implica que el ciclo es puro, y comienza ya desde el principio.

    He intentado en vano trabajar un poco más en esta idea, hasta demostrar que existe un ciclo que pasa por todos los puntos, pero no lo veo.

    Publica una respuesta
  8. Sive, si empiezas por una recta que pasa por el punto central no veo cómo la recta puede volver a encontrar el punto interior, por lo que éste no podrá ser INFINITAS veces centro de giro.
    En el planteamiento la recta gira SIEMPRE en sentido horario por lo que el remolino NO es reversible.

    Sebastián, la solución es única porque si hay un punto interior al polígono envolvente éste solo puede ser visitado por la recta si lo elegimos como inicial, es decir UNA sola vez.

    Publica una respuesta
  9. JJGJJG cuando digo que el remolino es reversible, quiero decir que puedo reconstruir mentalmente hacia atrás los movimientos que hizo la recta, girándola al revés, tanto como yo desee.

    Eso tiene implicaciones irrefutables a poco que se piense en ello, y una de ellas es que si el movimiento es cíclico (y es fácil demostrar que lo es), entonces lo es hacia adelante y hacia atrás (esta es la clave), y por tanto el remolino volverá a cualquier estado inicial del que partamos.

    Conclusión: no importa el punto de giro, y la inclinación de la recta inicial, el remolino está condenado a volver a ese estado.

    Publica una respuesta
  10. Pienso que, llegados a este punto, y no en pos de mi deducción, existe una configuración en S que cumple las propiedades. No hay que olvidar que L es infinita, es decir, una recta (no un segmento). De ahí sería bello alcanzar una demostración matemática no basada en ejemplos que otorguen validez al predicado. Saludos.

    Publica una respuesta
  11. Podemos considerar que todas las rectas que, al girarlas sobre un mismo punto central, van a chocar con el mismo punto, son la misma a los efectos de este problema.

    Desde este punto de vista, en un punto dado sólo hay (n-1) rectas esencialmente diferentes, siendo n el número de puntos en el conjunto.

    Y en total, hay n(n-1) estados diferentes, con lo que este movimiento continuo, queda discretizado. Podemos verlo como simples cambios de estado, dentro de un número finito de estados posibles, y donde el estado siguiente depende exclusivamente del estado actual.

    Este enfoque permite demostrar inmediatamente (mediante una aplicación directa del principio del palomar), que el remolino acaba entrando en un ciclo repetitivo. Y tambien permite demostrar que los pasos que va tomando son calculables hacia atras, demostrando lo que ya dije, que la periodicidad es pura.

    Mi intuición me dice que el paso que me falta para terminar de demostrarlo, entra dentro del álgebra, que es una rama de las matemáticas que sólo he tocado superficialmente (pero ahí ando con los PDF de Iborra), y con la que aún me siento torpe.

    Pero sólo es un pálpito.

    Publica una respuesta
  12. Si se empieza con un vértice de la envolvente convexa del conjunto de puntos y con una recta que no atraviese a dicha envolvente, el proceso es ciclíco, pero jamás pasa la recta por los puntos interiores. Por tanto, si del conjunto eliminamos los vértices de la envolvente convexa, y repetimos con el conjunto que queda de manera reiterada, como pelando una cebolla, hasta obtener un conjunto de puntos convexo, el “núcleo” del conjunto inicial, la primera recta en pasar por dos puntos del conjunto debe pasar por uno de este núcleo.

    Que el movimiento resultante es ciclico se deduce, comno indica Seve, de que esencialmente solo hay n(n-1) estados distintos, y que cada estado queda determinado por los dos anteriores. Por tanto, la longitud del ciclo es como máximo n(n-1)(n(n-1) -1).

    Lo que queda por ver es que todos los puntos son alcanzados alguna vez.

    Publica una respuesta
  13. Después de haberle dado bastantes vueltas al problema, he vuelto a llegar a la conclusión que expuse en mi primera respuesta: TODA configuración es posible.

    He aquí mi explicación, que por supuesto, puede ser errónea y agradeceré las correcciones que sean necesarias:

    – La conclusión de mi razonamiento, llevado a cabo por reducción al absurdo, es que si no existe una configuración en remolino de los Xi€S, con i=1,2,..,n, es porque tres de ellos son colineales; obviamente, esto contradice al enunciado y es prueba suficiente para afirmar que, al menos, existe ‘alguna configuración posible’ (yo dije que todas podían serlo).

    – Sive planteó un muy buen argumento, sobre el cuál he estado pensando de tanto en tanto: un triángulo de vértices X1,X2,X3 y un punto interior, X4. En teoría, si comenzamos el proceso de remolino desde alguno de los vértices, parece ‘obvio’ que la recta L jamás tocará al punto interno.

    – Sin embargo, pienso que hemos ¿olvidado? que L es una recta, no una semirrecta ni un segmento, es decir, puede topar con algún Xi por ambas partes, pues L es infinita (es una recta). Es decir, si tuviésemos la hipotética recta x= 1 que pasa por X4, al hacerla virar sobre éste, se trasladaría, tanto la parte ‘superior’ de la recta que pasa por X4 como la inferior que pasa por el mismo.

    – Tomemos el buen ejemplo de Sive: un triángulo equilátero de vértices X1,X2,X3 (X2 y X3 sobre el eje de abscisas) y un punto interno, elegido por mí al azar, X4, situado en el ortocentro del mismo. Si L pasa por X4, iniciemos el proceso de remolino: el primer punto de S con el que topa es, en este caso particular, X3, el vértice izquierdo que, por comodidad, situaré en (0,0).

    – Desde (0,0), rotamos L y ‘supuestamente’ toparía con X1 (considerado, en este caso, el vértice ‘cumbre’ del triángulo). Pero esto no es cierto: L toparía antes con el otro vértice X2, sobre las abscisas, puesto que la distancia de X4 a X2 es menor que la de X2 a X1; recordemos, es una recta, se prolonga al infinito en ambos sentidos a partir del punto.

    – Una vez topado X2, la recta viraría y toparía de nuevo con X4. Si L vuelve a virar, se toparía con X1 antes que con X3, pues L es, en este caso, la mediatriz del segmento X3-X1. Si se vuelve a virar sobre X1, la recta L topa antes con X3 que con X2, ya que L es mediatriz del segmento X2-X3. Y de vuelta a X2, el proceso se reproduce de forma indefinida.

    Con lo cuál, tras dos garabatos y mi anterior demostración, concluyo que todo punto que cumple las condiciones de S es un eje de giro de L de forma infinita.

    Publica una respuesta
  14. Bonito problema. Quizá ayude indagar qué sucede con el número de puntos situados
    a cada lado de la recta durante la ejecución del remolino…

    Publica una respuesta
  15. Sí, Sive. Se resuelve, creo que fácilmente, a partir de esa pista.

    Publica una respuesta
  16. Que no estén los puntos 3-alineados implica que disponiendo en primer lugar de ciertos puntos envolventes, los nuevos que vayamos añadiendo en el interior en proceso de “cebolla”, como bien indica Ignacio, formen ángulos correlativos cada vez menores entre ellos, (tendientes a 0 pero jamás llegando, ya que no puede haber colinealidad, conforme vamos añadiendo puntos cada vez más interiores). Esto implica que, cogiendo uno de los puntos interiores cuya recta l encima de él como centro sitúa los mismos puntos a lado y lado de las semirrectas formada por dicho punto, al girar, va encontrando primero los puntos cuya recta l forma un ángulo menor. Como este proceso de construcción de los puntos del conjunto se ha hecho correlativamente de manera que no hubiera colinealidad, esta condición asegura que la linea pasará por todos los puntos ya que la línea barre, en su giro periódico de 360º, todos los posibles ángulos que formen tres puntos cualesquiera del conjunto S. Evidentemente este proceso no puede ocurrir si tomamos un punto de la envolvente y “subenvonvelntes” de las subsecuentes capas de cebolla”, por la misma construcción.

    Dicho de otra manera, como no hay ningún punto colineal a otros dos. Las subenvolventes dibujan una sucesión de polígonos cuyas diagonales no cortan con otros puntos de envolventes exteriores. La línea l, si nos fijamos, va dibujando cada una de estas diagonales sucesivas.

    Publica una respuesta
  17. El problema dice claramente que la demostración pide que SE PUEDE ELEGIR un punto P€S y una recta L que pase por él con tal que el proceso de remolino se reproduzca infinitamente en todos los puntos Xi€S como ejes de giro, cumpliendo éstos que 1) sean finitos y 2) no haya tres puntos colineales. Si se trata de una demostración formal matemática, no verbal, ¿por qué no se da como válida la primera solución que propuse?

    Quizá @Gaussianos tenga algo que añadir. Pero, con toda la modestia, pienso que el problema está resuelto desde la primera demostración…

    Publica una respuesta
  18. Asumimos un sentido en la recta que gira, lo que nos permite hablar de los semiplanos izquierdo y derecho separados por la recta. ( y distinguimos como diferentes las direcciones giradas 180º).

    El conjunto de direcciones de las rectas que unen 2 puntos de S es finito.
    Llamamos dirección general a una dirección (de 0º a 360º) que NO esté en ese conjunto.

    La observación clave es que durante el remolino el número de puntos situados a un lado de la recta (por ejemplo el izquierdo), cuando la recta está en una dirección general, es constante.

    Por otro lado para cada dirección general en el plano existe un único punto P de S que deja exactamente m puntos de S a la izquierda de la recta (m \in \{0,1,2,\ldots, card(S)-1\}), porque desplazando la recta paralelamente a esa dirección los puntos del semiplano aumentan de 1 en 1.

    De donde se concluye que:

    Si partimos de una recta que pasa por un punto P de S y que deja a un lado exactamente m puntos de S, después de girar la recta 360º en la ejecución del remolino, la recta vuelve a la posición inicial después de haber pasado al menos 1 vez por todos los puntos de S por los que pasa al menos una recta que deja a un lado exactamente m puntos de S.

    Para resolver el problema basta entonces con demostrar que existe un m tal que por cada punto de S pasa una recta que deja exactamente m puntos de S a un lado de la recta. Pero eso es fácil tomando m = \lfloor card(S)/2 \rfloor.

    Publica una respuesta
  19. @fede, buenísima. Trabajé en tu pista pero no caí en la cuenta de que, para cada inclinación, sólo nos valía punto que dejase a cada lado el mismo número de puntos, y que por tanto, en una rotación tenían que usarse todos necesariamente.

    @Sebastian, yo sólo puedo hablar por mí. En mi caso, la única demostración que he entendido, es la de fede. No digo ni que sean incorrectas, ni que sea culpa vuestra.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Hoy os traigo el segundo problema de la IMO 2011 celebrada en Amsterdam durante…

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 *