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

Segundo problema de la IMO 2013 celebrada en Colombia. Ahí va:

Una configuración de 4027 puntos del plano, de los cuales 2013 son rojos y 2014 azules, y no hay tres de ellos que sean colineales, se llama colombiana. Trazando algunas rectas, el plano queda dividido en varias regiones. Una colección de rectas es buena para una configuración colombiana si se cumplen las dos siguientes condiciones:

  • ninguna recta pasa por ninguno de los puntos de la configuración;
  • ninguna región contiene puntos de ambos colores.

Hallar el menor valor de k tal que para cualquier configuración colombiana de 4027 puntos hay una colección buena de k rectas.

Que se os dé bien.

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.

16 Comentarios

  1. Creo que la respuesta es k=\log_2(4027). La idea que se me ocurre básicamente es que primero trazas una línea de tal manera que 2013 puntos queden de un lado y 2014 del otro. Luego, continuamos trazando líneas con esta idea hasta que haya un solo punto en cada región.

    Publica una respuesta
  2. Sergio: pareces dar por supuesto que con cada linea puedes dividir en dos cada una de las regiones previas. Por supuesto, eso no es verdad (ya es falso para 3 lineas).

    Publica una respuesta
  3. Lindo problema. Una solución simple sería: toma cada par de puntos rojos, y encierralos entre dos lineas paralelas (paralelas a la linea que los une, y a una distancia lo suficientemente pequeña para que no entre otro punto). Esto llevaría 2013 x 2012 lineas. Por supuesto, esto no debe ser óptimo.

    Publica una respuesta
  4. Siguiendo el razonamiento de hernan, a mí me salen 2014 líneas.
    Cada par de líneas paralelas separadas un epsilon tan pequeño como se quiera encierran dos puntos azules. Si dividimos el conjunto de 2014 puntos azules en 1007 pares, con dos líneas que encierran cada par, tendremos 2014 líneas.

    Publica una respuesta
  5. En realidad también valdría con 2013 líneas siempre.
    Si podemos aislar un punto rojo con una única línea (hay un punto rojo en la envolvente convexa) aplicamos el procedimiento anterior a los 2012 puntos rojos restantes y necesitaremos 2012 +1 = 2013 líneas.

    Si no pudiéramos aislar un punto rojo con una única línea implicaría que en la envolvente convexa sólo hay puntos azules, con lo que nos garantizamos que con una primera única línea podríamos aislar al menos dos puntos azules, de nuevo reduciendo el problema a 2012 puntos, esto es 2012 +1 líneas.

    Publica una respuesta
  6. El más claro resultado que pude haber hallado es el siguiente:
    Dos líneas de puntos paralelas separadas cada color por una recta en el centro de ellas, y una recta paralela en cada extremo; así tendremos dos grandes grupos de configuraciones de puntos. Imaginémonos que todos los 2013 puntos rojos estén a la izquierda del plano (-x) separadas por la línea vertical (y), mientras que todos los 2014 puntos azules estén a la izquierda (x); siendo que debe cumplirse “la colombiana” tendremos que crear dos filas de puntos hasta llegar a la cantidad correspondiente.
    Entonces tenemos: k=2013 (y un punto queda libre, del grupo de puntos rojos) de colección buenas.
    Bueno, es como yo comprendo.

    Publica una respuesta
  7. hernan:

    Claro que se puede, simplemente si el número de puntos a separar es 2n+1, pones n puntos de un lado y n+1 del otro, como lo expliqué al iniciar el algoritmo.

    Publica una respuesta
  8. La solución de 2013 que puse arriba es correcta… pero incompleta. Sólo indiqué que cualquier combinación de puntos se podía particionar con 2013 líneas, pero como bien indicaba hernan, había que demostrar que ese número fuera el menor k.

    Para ello bastaría con encontrar una configuración concreta de puntos para la que hicieran falta 2013 líneas sí o sí. Como la solución tiene que valer para cualquier configuración, la solución pedida sería 2013.

    Ya encontré dicha configuración. Luego la pongo 😉

    Publica una respuesta
  9. Como idea:

    Pensemos en un polígono convexo de 4027 lados, cuyos vértices (2013 rojos y 2014 azules) sean v_{1,}v_{2,}\ldots_{,}v_{4027}

    Las aristas del polígono serían \overline{v_{1}v_{2}},\:\overline{v_{2}v_{3},}\ldots\:,\:\overline{v_{4027}v_{1}}

    A cada uno de los vértices v_{i} le llamamos r_{i} si es rojo y a_{i} si es azul.

    Así, los aristas del polígono serían, por ejemplo \overline{r_{1}a_{2}},\:\overline{a_{2}r_{3},}\ldots\:,\:\overline{a_{4027}r_{1}}

    Ahora recorremos los lados de la figura a partir de un vértice arbitrario hasta volver al punto de partida (en sentido horario o antihorario).

    En caso de que los extremos del arista sean de color distinto (\overline{r_{i}a_{j}} ó \overline{a_{i}r_{j}}) insertamos un punto intermedio  i_{m} : \overline{r_{i}a_{j}}\Rightarrow\overline{r_{i}i_{m}a_{j}}

    En caso de que los extremos del arista sean del mismo color (\overline{a_{i}a_{j}} ó \overline{r_{i}r_{j}} ) lo dejamos inalterado.

    Lo puntos intermedios serán entonces i_{1,}i_{2,}\ldots_{,}i_{p} , donde p es la cantidad total de puntos intermedios.

    Para dividir el plano en regiones que no contengan puntos de ambos colores trazamos líneas \overline{i_{1}i_{p}},\:\overline{i_{2}i_{p-1}},\ldots\:,\:\overline{i_{\frac{p}{2}}i_{\frac{p+2}{2}}}

    Serán necesarias un total de \frac{p}{2} líneas para dividir el plano en \frac{p+2}{2} regiones.

    El caso más sencillo sería que tuvieramos primero los 2013 vértices rojos y luego los 2014 azules (o viceversa).

    Tendríamos 2 puntos intermedios, es decir p=2 y sería necesaria \frac{2}{2}=1 línea.

    El caso más crítico sería que los vértices rojos y azules se alternaran. En ese caso tendríamos 4026 aristas tipo \overline{r_{i}a_{j}} (incluido el  \overline{a_{2014}r_{1}}) y una  \overline{a_{2013}a_{2014}} .

    Por lo tanto, habría p=4026 puntos intermedios y se necesitan \frac{4026}{2}=2013 líneas para cumplir las condiciones de la «Colombiana».

    Publica una respuesta
  10. Creo que hay una manera de decir lo que dice elchen00 de forma más compacta; pero que supongo que acaba siendo lo mismo dicho de otra manera.

    Suponemos una configuración de los 4027 puntos sobre una circumferencia (por ejemplo, en un polígono regular) donde los pondremos intercalados rojo y azul (obviamente habrá dos azules consecutivos). Hay 4026 aristas del polígono con extremos de distinto color, y está claro que por cada una de las aristas cruza una recta de las que separa en regiones (sino, dos puntos de distinto color estarían en regiones distintas). Como cada recta pasa, como mucho, por dos aristas distintas (polígono convexo), y hay 4026 aristas con extremos de distinto color; son necesarias, al menos, 2013 rectas.

    Como dice A.M., con 2013 se puede siempre (según su método), luego el número que buscamos es 2013.

    Publica una respuesta
  11. Polígono convexo y circunferencia funcionan. Pero que pasaría si tuviéramos una figura tipo estrella, por ejemplo? y en general no convexa?, también se pueden disponer de sa manera los puntos.

    Publica una respuesta
  12. La propuesta de A.M. de aislarlos por parejas demuestra que con 2013 líneas como máximo resolvemos cualquier configuración de puntos.
    La cofiguración de polígono inscrito propuesta por elchen00 necesita precisamente 2013 líneas. Luego 2013 es un mínimo. Problema resuelto porque el mínimo para una configuración concreta y el máximo para cualquier configuración coinciden. El resto de configuraciones necesitarán 2013 o menos líneas.

    Publica una respuesta
  13. El mismo mecanismo usado por elchen00 vale para el caso de un polígono cóncavo.

    Dibujamos un polígono convexo (envolvente) con los puntos exteriores del primer polígono cóncavo. Ahora, por un punto de la cóncavo trazamos una recta que va desde ese primer punto al diametralmente opuesto de dicho polígono cóncavo si en ese polígono hay un número par de puntos, o por el casi diametralmente opuesto si hay un número impar. Ahora, vamos trazando paralelas solidarias a esa primera recta con los puntos restantes (rayando el polígono). Nos quedará ahora un polígono dividido en regiones con puntos dentro de diferente color o no. Ahora aplicamos el mismo razonamiento qur elchen00 con los puntos interiores de dichas regiones, dibujando líneas interiores, entre punto y punto de diferente color de los interiores, y que sean paralelas también a las primeras líneas del rayado anterior. Nos quedará una división numéricamente equivalente a la de elchen00 con 2013 líneas interiores.

    Publica una respuesta

Trackbacks/Pingbacks

  1. Bitacoras.com - Información Bitacoras.com Valora en Bitacoras.com: Segundo problema de la IMO 2013 celebrada en Colombia. Ahí va: Una configuración de…

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 *