Vamos con el problema de la última semana del año 2010:
Se tienen 
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.
[…] This post was mentioned on Twitter by gaussianos, Andrés Aguilar. Andrés Aguilar said: Puntos rojos y azules http://bit.ly/hBGlqn […]
Información Bitacoras.com…
Valora en Bitacoras.com: Vamos con el problema de la última semana del año 2010: Se tienen 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. Dem……
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?
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… Lee más »
Una figura para el argumento de Carlos: ( AC+BD < AD+BC)
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.
Muy buena Carlos Luna. Quería comentar otra forma: de las 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… Lee más »
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… Lee más »
JJGJJG, me ha gustado tu razonamiento. Si no he entendido mal, parece que indicas el valor
como número de emparejamientos azul-rojo posibles sin cruces en total. Sin embargo, tampoco parece válido incluso en el caso 
. 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.
Con la configuración de 4+4 puntos de la figura siguiente, existen 18 emparejamientos
sin cruces (y 6 con algún cruce).
El grafo bipartito completo
que resulta de unir los puntos rojos con los azules hace pensar que si 
es el «numero de cruce rectilíneo» para el grafo G, 
.
¿ Cual será el valor de
?
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.
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… Lee más »
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).
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
porque con esa configuración se consiguen 16 cruces para 
, 
según MathWorld y 
.