Puntos rojos y azules

Vamos con el problema de la última semana del año 2010:

Se tienen 2n puntos en el plano, tales que la mitad de ellos están coloreados de rojo y la otra mitad de azul. Además, tres puntos cualesquiera no están alineados. Demostrar que es posible emparejar con segmentos los puntos rojos con los azules, de modo que los segmentos formados no se intersequen (en puntos que no sean los propios vértices). ¿De cuántas formas posibles puede hacerse un emparejamiento en las condiciones anteriores?

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.

11 Comentarios

  1. Tengo una duda, quiza entendi mal, por ejemplo si hay 4 puntos, en el mejor de los casos existen dos formas de emparejar los puntos, pero en el peor de los casos exite 1 forma. Entonces a que e refiere con de cuantas formas se lo puede hacer?

    Publica una respuesta
  2. Existe al menos una manera de emparejarlos sin cruces que se caracteriza por ser el emparejamiento de menor longitud total:

    * Hagamos un emparejamiento al azar.
    * Si no existe ningún cruce hemos terminado.
    * Si existe algún cruce habrá al menos 4 puntos implicados, 2 rojos y 2 azules.
    * Procedemos a “descruzar” ambas parejas. Esta operación reduce la longitud total del emparejamiento.
    * Dado que hay un número finito de puntos y que la longitud del emparejamiento siempre ha ido decreciendo sabemos que estas operaciones terminarán en un número finito de pasos.
    * Una vez finalizadas tendremos un emparejamiento sin cruces.

    Publica una respuesta
  3. Una figura para el argumento de Carlos: ( AC+BD < AD+BC)

    \setlength{\unitlength}{0.8cm}\begin{picture}(8,6)\put(1,3){\circle*{0.3}}\put(1,3.3){A}\put(7,2){\circle{0.3}}\put(7,2.3){D}\put(3,1){\circle*{0.3}}\put(2.5,1){B}\put(6,5){\circle{0.3}}\put(6,4.4){C}\put(1,3){\line(6,-1){6}}\put(1,3){\line(5,2){5}}\put(3,1){\line(4,1){4}}\put(3,1){\line(3,4){3}}\end{picture}

    Por otro lado para el conjunto de 2n puntos { (i,0) rojos , (i,1) azules | i=1,…n } existe un único emparejamiento que no tenga cortes.

    Publica una respuesta
  4. Muy buena Carlos Luna. Quería comentar otra forma: de las n! formas posibles de emparejar puntos rojos y azules debe existir al menos un emparejamiento que minimice la longitud de los segmentos y, por la desigualdad triangular, este emparejamiento no puede tener cruces (ya que la suma de diagonales en un cuadrilátero es mayor que la suma de lados opuestos).

    La cuestión sobre cuántos emparejamientos son posibles parece más complicada, por el hecho de que pueden haber soluciones libres de cruces sin ser de longitud mínima. Me parece que fede ha asumido que los puntos azules y rojos pueden separarse en un mismo semiplano, cosa que no tiene porqué darse. Por ejemplo si consideramos como puntos rojos el (0,0) y el (1,2), y como puntos azules el (0,1) y el (2,2), entonces hay dos (2!) emparejamientos posibles.

    Sin embargo, me parece que para n>2 el número de emparejamientos posibles es menor que n! (por ejemplo, para n=3 me parece que sólo pueden darse como máximo 5 emparejamientos sin cruces).

    Publica una respuesta
  5. Colocamos n puntos de un color e un n-ágono regular y n puntos del otro color en otro n-ágono regular de menor tamaño, concéntrico con el anterior y girado un semiángulo respecto del grande. Si unimos cada punto del exterior con el primero que se divisa del interior obtendremos un emparejamiento sin cruces- lo mismo si unimos todos con el segundo, y así sucesivamente.
    El número de vértices del polígono interior que se ven desde el lado de un vértice del exterior es n/2 + 1 para n par y de (n + 1)/2 para n impar. Este es, pues el máximo de emparejamientos posible sin cruces.

    Publica una respuesta
  6. JJGJJG, me ha gustado tu razonamiento. Si no he entendido mal, parece que indicas el valor n\cdot \lceil \frac{n+1}{2}\rceil como número de emparejamientos azul-rojo posibles sin cruces en total. Sin embargo, tampoco parece válido incluso en el caso n=3. Para los triángulos equiláteros concéntricos, habría un emparejamiento no válido, que es el que se obtiene al unir cada vértice exterior con el correspondiente interior “no visible”. Es decir, que en este caso, también habrían 5 emparejamientos en lugar de 6.

    Publica una respuesta
  7. Con la configuración de 4+4 puntos de la figura siguiente, existen 18 emparejamientos
    sin cruces (y 6 con algún cruce).

    \setlength{\unitlength}{0.8cm}\begin{picture}(8,6)\put(3,3){\circle*{0.2}}\put(4,3){\circle*{0.2}}\put(6,3){\circle*{0.2}}\put(7,3){\circle*{0.2}}\put(5,1){\circle{0.2}}\put(5,2){\circle{0.2}}\put(5,4){\circle{0.2}}\put(5,5){\circle{0.2}}\end{picture}

    El grafo bipartito completo K_{4,4} que resulta de unir los puntos rojos con los azules hace pensar que si \bar{v}(G) es el “numero de cruce rectilíneo” para el grafo G, \bar{v}(K_{4,4})=4.

    ¿ Cual será el valor de \bar{v}(K_{5,5}) ?

    Publica una respuesta
  8. Yo no veo que el algoritmo de Carlos Luna funcione, porque asume implícitamente que cuando se “descruzan” dos segmentos, disminuye el número de cruces, lo cual sólo ocurre si el cuadrilátero formado por los cuatro puntos en cuestión no está cortado por ningún otro segmento. En realidad, el número de cruces puede aumentar, mantenerse o disminuir.

    Publica una respuesta
  9. A mi, intuitivamente, también me cuesta ver que dicho algoritmo sea la solución, pero lo que reduce el algoritmo no es el número de cruces, sino la longitud total de los segmentos implicados.

    Al descruzar un cruce cualquiera, la longitud total disminuye, da igual que aún queden cruces (e incluso más), los vas descruzando y como forzosamente la longitud total disminuye (al hacer un descruzamiento cualquiera), llegará un momento en el que “no puede disminuir la longitud total”, en ese momento, tienes la solución de emparejamiento óptima.

    La aclaración de fede asegura esta convergencia.

    A mí me ha encantado el algoritmo.

    Publica una respuesta
  10. Lo que ya no veo tan claras son las soluciones al número de soluciones.

    El número total de soluciones para una configuración de puntos dada está acotada superiormente, sí, por combinatoria, pero puede ser muy inferior para cada configuración concreta.

    Por tanto, tal como lo pide el enunciado, no creo que puedan (en general) calcularse las soluciones más que enumerándolas (con otro algoritmo).

    Publica una respuesta
  11. cullero, la suma de las longitudes de los segmentos disminuye en cada paso por la desigualdad triangular.

    Respecto al número de emparejamientos sin cruces, si a la configuración de la figura anterior añadimos un punto blanco encima de los blancos y uno negro a la derecha de los negros, según un primer cálculo sin revisar me salen 46 emparejamientos sin cruces. ( y 74 con cruces).

    Además \bar{v}(K_{5,5}) = 16 porque con esa configuración se consiguen 16 cruces para K_{5,5}, cr(K_{5,5}) = 16 según MathWorld y cr(G) \le \bar{v}(G).

    Publica una respuesta

Trackbacks/Pingbacks

  1. Tweets that mention Gaussianos.com: Puntos rojos y azules -- Topsy.com - [...] This post was mentioned on Twitter by gaussianos, Andrés Aguilar. Andrés Aguilar said: Puntos rojos y azules http://bit.ly/hBGlqn [...]
  2. Bitacoras.com - Información Bitacoras.com... Valora en Bitacoras.com: Vamos con el problema de la última semana del año 2010: Se tienen puntos…

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 *