Autor Tema: Puntos en el plano

0 Usuarios y 1 Visitante están viendo este tema.

19 Julio, 2008, 12:32 am
Leído 1141 veces

alinfinitum

  • $$\pi$$
  • Mensajes: 21
  • Karma: +0/-0
  • Sexo: Masculino
hola, este problema suena inofensivo, pero creo que no lo es tanto, o necesita de alguna idea feliz:

 Considera n puntos rojos y n puntos azules en el plano, no tres de ellos colineales. Demuestra que es posible unir cada punto rojo con uno azul mediante un segmento de recta, de tal manera que ningún para de segmentos se intersecte.

21 Julio, 2008, 11:53 am
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,087
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

 En un primer momento podríamos razonar así. Supongamos que tenemos una configuración de segmentos con el mínimo número de intersecciones posibles.

 Dada una intersección podríamos "arreglarla" así:



 de manera que obtendríamos una configuración con menos intersecciones. El problema es que nada nos asegura (o al menos no está claro) que arreglando esta no nos aparezcan nuevas intersecciones.

 La "feliz idea" puede ser replantearlo así: prueba que una configuración de segmentos cuya suma de distancia sea mínima cumple la propiedad pedida. La idea es que si se cruzan dos segmentos el arreglo anterior nos da una nueva configuración con menor distancia.

Saludos.

24 Julio, 2008, 02:27 am
Respuesta #2

alinfinitum

  • $$\pi$$
  • Mensajes: 21
  • Karma: +0/-0
  • Sexo: Masculino
Sí, muchas gracias, era lo q faltaba.