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
tal que para cualquier configuración colombiana de 4027 puntos hay una colección buena de
Que se os dé bien.
¿Te ha gustado la entrada? Puedes invitarme a un café, Gauss te lo agradecerá 😉
Información Bitacoras.com
Valora en Bitacoras.com: 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. Trazand…
Creo que la respuesta es
. 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.
¿Quién puede explicar este problema en español?
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).
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.
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.
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.
Me parece bien lo de AM. Pero dudo que sea optimo.
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… Lee más »
hernan:
Claro que se puede, simplemente si el número de puntos a separar es
, pones 
puntos de un lado y 
del otro, como lo expliqué al iniciar el algoritmo.
Sin embargo, ahora estoy casi seguro que estoy mal.
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 😉
Como idea: Pensemos en un polígono convexo de 4027 lados, cuyos vértices (2013 rojos y 2014 azules) sean Las aristas del polígono serían A cada uno de los vértices le llamamos si es rojo y si es azul. Así, los aristas del polígono serían, por ejemplo 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 ( ó ) insertamos un punto intermedio : En caso de que los extremos del arista sean del… Lee más »
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,… Lee más »
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.
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.
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… Lee más »