Puntos, rectas y un problema sin resolver que cualquier niño puede entender

Puntos, rectas y un problema sin resolver que cualquier niño puede entender

Éste es un problema de matemáticas que se puede explicar tranquilamente a un niño de primaria. Es ideal para que vuelvas por un rato a la infancia y juegues mientras intentas resolverlo. Sólo necesitas dibujar puntos y unirlos en línea recta.

Pero incluso lo más sencillo puede acabar complicándose y si sigues leyendo descubrirás cómo este problema se resiste a los esfuerzos de matemáticos de todo el mundo… desde hace 40 años.

Como ingredientes del problema te voy a dar un número de ciudades y un plano (una hoja de papel, una servilleta, una pantalla, sirve cualquier sitio donde puedas dibujar). El primer objetivo será:

Colocar cada ciudad, dibujada como un punto, donde queramos. Después, unir cada par de ciudades mediante una carretera en línea recta (un sueño para algunos, una pesadilla para otros ;-)).

¿Estás preparado para jugar? ¿Ya tienes con qué dibujar? Pues vamos a empezar por el caso en el que tenemos sólo 2 ciudades.

Hay que dibujar dos puntos, donde quieras, y unirlos por una carretera recta. Ya lo sé, ya, es muy fácil… pero cada uno lo habrá dibujado de una forma; unos en vertical, otros en horizontal, algunos con otro ángulo. Quizá hayas puesto los puntos muy cerca, o muy lejos, o ni una cosa ni otra.

Pero, independientemente de cómo lo haya dibujado cada uno, todos tendremos esencialmente el mismo dibujo. Esta «esencia» del dibujo es nuestro mapa de carreteras, que será igual para todos y que en este caso es un segmento:

Dos ciudades unidas por un segmento

¿Está claro, verdad? Pues ahora vamos con el caso de 3 ciudades. Hay que dibujar tres puntos y después unir cada par de ciudades mediante una carretera recta.

¿Lo tienes? Claro que sí. Otra vez cada uno lo habrá dibujado a su manera, pero todos tendremos un mismo mapa de carreteras, que en este caso es un triángulo:

Tres ciudades unidas todas entre sí

Para 4 ciudades la cosa se pone interesante. Te dejo un rato para que dibujes. Tic, tac, tic, tac. ¿Está? ¿No has hecho trampas? Me fío de ti.

Lo interesante del caso de 4 ciudades es que hay más de un mapa de carreteras:

  • Algunos habréis dibujado un cuadrilátero convexo, como el de la figura de la izquierda.
  • Otros habréis dibujado un triángulo con una cuarta ciudad en su interior, como el de la figura de la derecha.

Cuatro ciudades unidas todas entre sí

Como no habíamos puesto ninguna regla más, las dos soluciones están bien… pero en realidad una de ellas es más interesante que la otra.

El mapa de carreteras de la izquierda tiene un cruce y el de la derecha no. Como un cruce de carreteras es un peligro, vamos a intentar evitar los cruces. Así, nuestro nuevo objetivo será:

Colocar las ciudades de manera que, al unir cada par de ellas en línea recta, no aparezca ningún cruce.

¿Está claro, verdad? Pues ahora vamos a por el caso con 5 ciudades. Otro rato para que dibujes; tic, tac, tic, tac. ¿Has acabado? No me lo creo, inténtalo otro rato. Tic, tac, tic, tac. ¿Cómo? ¿Que no lo consigues? No te preocupes…

Para el caso de 5 ciudades hay tres posibles mapas de carretera:

  • Un pentágono convexo (figura izquierda).
  • Un cuadrilátero con un punto dentro (figura central).
  • Un triángulo con dos ciudades en su interior (figura derecha).

Cinco ciudades unidas todas entre sí

¡¡Y en todos los mapas de carretera hay algún cruce!! Resulta que para 5 ciudades no se puede encontrar una solución sin cruces (si quieres, puedes leer por qué al final de la entrada).

Además, a partir de 5 ciudades (6, 7, 8, las que sean) cualquier mapa de carreteras contendrá un mapa de carreteras con 5 ciudades. Por lo de antes, éste tendrá cruces… así que a partir de 5 ciudades cualquier mapa de carreteras tendrá cruces.

Así que tendremos que cambiar otra vez de objetivo, pero te prometo que éste es el definitivo:

Colocar las ciudades de manera que, al unir cada par de ellas en línea recta, haya el menor número posible de cruces.

En el caso de 5 ciudades el mapa de carreteras que menos cruces tiene es el de la derecha, que tiene sólo uno, mientras que el del centro tiene tres y el de la izquierda tiene cinco.

¿Está claro el problema? ¿Te animas a seguir jugando? Puedes pensar un rato cómo colocar 6 ciudades de manera que al unirlas haya el menor número posible de cruces.

Imagínate que, después de unos cuantos intentos, lo mejor que tienes es un dibujo con 4 cruces. ¿Cómo puedes saber si has ganado? ¿Puede ser que otro jugador tenga mejor ojo y consiga hacerlo con sólo 3 cruces?

Una manera de saber si has conseguido el menor número de cruces es conocer todos los mapas de carretera distintos que puede haber. Para 6 ciudades hay 16 mapas de carretera distintos; si consigues dibujarlos todos, bastará con mirar cuál tiene menos cruces.

Pero, claro, no es fácil dibujar esos 16 mapas de carretera distintos, así que te voy a dar los resultados (no los dibujos :-)) desde 2 hasta 11 ciudades:

Ciudades

Mapas de carretera

Menor número de cruces

2

1

0

3

1

0

4

2

0

5

3

1

6

16

3

7

135

9

8

3.315

19

9

158.817

36

10

14.309.547

62

11

2.334.512.907

102

¿Cuántos cruces habías conseguido tú para 6 ciudades? ¿Habías conseguido hacerlo con sólo 3 cruces?

Como ves, el juego se va complicando y para 11 ciudades el menor número de cruces es 102… que ya tiene que ser difícil de dibujar.

Y eso que tenemos la suerte de poder mirar en la tabla y no tener que dibujar todos los mapas de carretera distintos. Porque para 7 ciudades ya tendríamos que dibujar 135 mapas de carretera. Y para sólo 11 puntos hay ¡¡más de 2.000 millones de mapas de carretera distintos!!

Así que, aunque el problema es sencillo, se complica rápidamente a medida que crece el número de ciudades. Este problema se conoce como el problema del número de cruce rectilíneo del grafo completo y fue propuesto por Erdős y Guy en 1973. A día de hoy, 40 años después, sigue sin conocerse la solución para 28 ciudades… y eso que cualquier niño puede entender el problema.

Puedes seguirnos en Twitter, Facebook y Google +.

Nota 1: Si te animas a intentar conseguir el menor número de cruces para 6, 7, o incluso 8 ciudades (puedes comprobar tu resultado con la tabla), nos haría mucha ilusión que nos lo enviaras a cifrasyteclas@km77.com. Así podremos ir completando la galería, que puedes ver al final de la entrada.

Nota 2: Esta entrada participa en la edición 3.1415926535 del Carnaval de Matemáticas, cuyo blog anfitrión es La Aventura de la Ciencia.

Nota 3: Esta entrada ha llegado al Olimpo en Divoblogger.

Nota 4: Esta entrada ha llegado a portada en Menéame.

Nota 5: Esta entrada ha llegado a portada en Divúlgame.

Nota 6: Gracias a @DavidOrti por avisarme de una errata; desde 1973 hace 40 años y no 30 🙂 

Para saber más:

Si te da por poner tres puntos alineados, la carretera que une las dos ciudades de los extremos pasaría por encima de la ciudad intermedia.  Como eso no tiene mucho sentido, en esta entrada (y en el problema del número de cruce) se excluye esa posibilidad.

Para demostrar que el caso de 5 ciudades no se puede hacer sin cruces puedes utilizar la Fórmula de Euler; en este documento (pdf) puedes ver cómo. Este grafo para 5 ciudades se llama grafo completo (K_5) y el matemático polaco Kazimierz Kuratowski demostró que es una pieza clave para saber cuándo un grafo se puede dibujar sin cruces. Puedes leer dos entradas interesantes al respecto en este enlace o en este otro.

A cada mapa de carreteras, que en el fondo es cada manera distinta de colocar un mismo conjunto de puntos, se le llama tipo de orden. Puedes encontrar todos los tipos de orden hasta 10 puntos en este enlace. El de 11 puntos es un fichero que ocupa ¡¡96GB!!

A partir de 11 ciudades ni si quiera se sabe cuántos mapas de carretera distintos hay. Así que no se puede decidir el menor número de cruces simplemente comprobando todos los mapas. Hacen falta otras técnicas y a veces se sabe cuál es el menor número de cruces pero no se sabe cómo dibujarlo.

En esta página puedes ver una tabla que, hasta 100 puntos, te dice el menor número de cruces posible cuando éste se conoce, o bien el menor número de cruces que se ha conseguido, cuando no se conoce cuál es el menor posible. Como puedes comprobar, para 28 puntos hay un dibujo con 7234 cruces, pero no se sabe si hay alguno con menos cruces (si consigues uno con 7233 te harás famoso ;-)).

Se sabe que para conseguir el menor número de cruces la envolvente convexa debe ser triangular. Es decir, que la capa exterior debe formar un triángulo. Aunque esto se intuye fácilmente después de un par de dibujos, no se consiguió demostrar hasta 2006 en este artículo (en el que tuve el gusto de participar).

Los problemas sobre minimizar el número de cruces tienen aplicaciones, por ejemplo, en el diseño de circuitos integrados (VLSI).



34 respuestas a «Puntos, rectas y un problema sin resolver que cualquier niño puede entender»

  1. Avatar de Fanso
    1. Avatar de David Orden

      @1 Fanso: ¡Muchas gracias! 🙂

  2. Avatar de Jose M.
    Jose M.

    Mi solución para 6 ciudades, sin cruces:

    O——-O——-O——-O——-O

    (Vale, es un poco perverso)

    1. Avatar de David Orden

      @3 Jose M.: Gracias, buen intento, pero sólo hay 5 ciudades en ese dibujo 🙂 Además la ciudad del extremo izquierdo no está unida con la del extremo derecho. Por eso en el primer párrafo de «para saber más» aclaro que no consideramos la opción de que haya 3 puntos alineados, porque implicaría tener que hacer una carretera por encima de una ciudad… y eso no tiene mucho sentido. 🙂

  3. Avatar de David
    David

    Pues yo he pensado lo mismo que Jose M. Nadie ha dicho que tenga que formar una figura geométrica, pueden estar todas en línea recta.
    La primera y la última sí están conectadas, pero hay que pasar por el resto. Un ejemplo es una autopista, que es una línea que conecta varias ciudades, es de doble sentido y no tiene cruces.

    1. Avatar de David Orden

      @5 David: En ese dibujo no hay una carretera directa entre las ciudades de los extremos. Para hacerla habría que pasar por encima de las ciudades intermedias.

  4. Avatar de Manolo
    Manolo

    En 3D es muy facil, o sea, que si valen tuneles la cosa se simplifica, pero hasta que nivel?. Creo que con 15 puntos ya es dificil….

  5. Avatar de joseenrique
    joseenrique

    Para solucionar el problema dios invento las curvas…

  6. Avatar de David
    David

    @David Orden : Por encima? o mejor cruzarlas no? entiendo el trasfondo del «problema» matemático, pero creo que el enunciado no queda claro, porque si yo tengo esto:
    A====B
    o
    A====B====C
    Puedo llegar de A a C, obviamente pasaré por B, pero eso no impide que pueda llegar, ¿o si?
    En cualquier caso, buen artículo y explicación 🙂

    1. Avatar de David Orden

      @David: Pero en ese caso A y B no se unen directamente entre sí, como se pide (aunque en la vida real bastaría con lo que dices). Piensa en un circuito electrónico, donde puedes necesitar una unión directa entre A y B. Me alegra que te guste, gracias 🙂

  7. Avatar de Dante
    Dante

    ¿Habeis oído hablar de la casa de Nicolás? en Alemania soliamos hacerlo en el cole, das ist das hause von Nicolause…se trata de dibujar una casita con su tejado sin pasar por encima de ninguna línea trazada.

    1. Avatar de David Orden

      @11 Dante: Gracias por la información, no sabía en que Alemania se llamara así, pero tiene sentido. Ése es otro problema, el del ciclo euleriano, que también tiene que ver con grafos. Quedará para otra entrada 🙂

  8. Avatar de Luis
    Luis

    En el dibujo de 4 ciudades en triangulo hay un cruce en una ciudad, y dices que no se considera cruce ¿por qué no se puede hacer lo mismo en el de 5 ciudades en cuadrado ?

    1. Avatar de David Orden

      @12 Luis: No se considera cruce porque son carreteras que llegan a una ciudad y salen de ella, no se cruzan. En el dibujo de 5 ciudades hay 4 formando un cuadrado y 1 dentro; en ésa de dentro no hay un cruce, pero sí hay 3 cruces entre carreteras, un poco más arriba.

  9. Avatar de jose
    jose

    Yo lo he leído por encima y desde el principio he pensado en una red de triángulos… no se si esto cumple las premisas… creo que si, y no se consigue ningún cruce…

    1. Avatar de David Orden

      @13 Jose: Dínos qué entiendes por «red de triángulos». Puede que te estés acercando 🙂

  10. Avatar de Antonio A.
    Antonio A.

    Creo que el de Diego no es correcto, faltan ciudades por conectar.
    Un saludo

  11. Avatar de Óscar
    Óscar

    Quisiera saber si tiene sentido generalizar el problema a 3 dimensiones, o si en 3D siempre puede resolverse sin cortes.

    1. Avatar de David Orden

      @15 Óscar: En 3D podrías construir un puente cada vez que hubiera un cruce, con lo que ya no sería un cruce.

  12. Avatar de Paredero
    Paredero

    No estoy de acuerdo con las soluciones. Estais hablando de un espacio tridimensional todo el tiempo. se debe considerar que el planeta es una esfera, ergo se pueden unir los puntos de los extremos sin violar la característica de la recta.

    1saludo.

  13. Avatar de Javier Moltó

    David, (profe), tengo una pregunta.

    de los mapas de hasta 28 ciudades. De los que se sabe la solución, quiero decir.

    Cuántos mapas diferentes dan el mínimo número de cruces?

    De los 2,3 millardos de mapas que pueden hacerse con 11 ciudades.

    ¿Cuántos de ellos tienen 102 cruces?

    (A mí sólo se me ocurre situar la ciudades en los vértices de troncos de cono, para que no se alineen superpuestos, interpuestos o en línea, pero nada más. Me resulta imposible imaginar cómo puede haber tantos millones de mapas)

    1. Avatar de David Orden

      @21 Javier: Muy buena pregunta. Lo que se sabe está en la última columna de la tabla de este enlace. En particular, para 11 ciudades hay 374 mapas de carretera distintos con el mínimo número de cruces. Pero es una cantidad muy variable; para 10 ciudades hay 2 y para 12 ciudades hay sólo 1.

      Para intentar entender por qué hay tantos mapas se puede pensar en lo siguiente. Primero, dibuja un mapa de carreteras. Ahora mueve una de las ciudades (arrastrando las carreteras que llegan a ella). En cuanto esa ciudad que estás moviendo pase por encima de una carretera cualquiera, acabas de cambiar el mapa de carreteras. (Puedes verlo moviendo el punto rojo en alguna de las figuras de esta construcción interactiva).

      La idea intuitiva de lo que pasa es que cuando hay muchas ciudades hay también muchas carreteras y muchas maneras de mover el punto para obtener un nuevo mapa.

  14. Avatar de Santiago

    Una solución relativamente útil para el grafo K5 sería un cuadrado convexo con un punto en su centro, aunque así los dos pares de vértices opuestos no estarían unidos entre sí de manera directa, sino que habría que hacer una parada en el centro para llegar al otro lado.
    Todo esto es, claro, en R2 (plano), aunque si pensáramos estos problemas en una banda de Mobiüs las soluciones serían posibles hasta cierto punto (pues de la misma manera que en un plano común y corriente, después de cierto número de ciudades definitivamente tendría que haber algún cruce).
    Otra solución que se me ocurre es si ubicamos los puntos en un toro, que es como una banda de Mobiüs en tres dimensiones, pero acá sucedería lo mismo, aunque un toro es un situación un poco más «real», puesto que las ciudades y todos los elementos de nuestra vida en general se dan en un espacio.
    También se me ocurre que podríamos simplemente unir los vértices con líneas perversamente curvas y que no estuvieran todas niveladas (unas más altas que otras, otras por debajo de la tierra jeje, cosas por el estilo).
    ¡Muy interesante toda esta teoría de grafos!

  15. Avatar de daniela
    daniela

    necesito las aplicaciones de la recta de euler pero no las encuentro me podrian ayudar a buscar en que pagina lo puedo encontrar

  16. Avatar de lola
    lola

    como se llama este problema

    1. Avatar de David Orden

      @25 lola: El nombre del problema y la información sobre su origen está en el último párrafo antes de las notas 😉

  17. Avatar de Alejandro
    Alejandro

    Como puedo unir 4 puntos con tres lineas, empezando y terminando en el mismo punto sin levantar el lápiz. Asi están los puntos

    . .

    . .

  18. […] que tienes que diseñar una autovía o una vía férrea de alta velocidad. Seguro que intentarás que haya todas las rectas posibles, pero también tendrás que hacer alguna […]

  19. […] Si has estado dándole vueltas al caso con tres hornos y tres almacenes (o si ya lo conocías) seguro que te interesará saber que sí se puede resolver sin cruces en la banda de Möebius (nos lo contó Gaussianos) y en el toro (nos lo contaron en Trablog). Quizá también te interese leer una entrada anterior en la que hablé sobre cómo dibujar con pocos cruces otro tipo de estructura. […]

  20. Avatar de MARI
    MARI

    yo tengo 11 años soy de ecuador me gusta las matematicas y literatura me dudieran ayudar a resolver este problema
    . . . .
    . . . .
    . . . .
    . . . .
    unir los 16 puntos con 6 lineas sin alzar la mano
    😉 porfavor

  21. Avatar de valeria contreras
    valeria contreras

    hola mari, yo tambien necesito eso tu ya lo pudiste resolver pues ya lo escribiste desde el 2 de julio. te agradeceria mucho si me ayudaras ( :

  22. Avatar de Ernesto Gonzalez
    Ernesto Gonzalez

    Estimado maestro, estuve visitando su pagina y me deleite con el problemas de unir las ciudades con el menor numero de cruces y estoy trabajando para el caso de 6,7,8 ciudades para ver que figura geometrica me genera.
    Estoy seguro que sera divertida la experiencia, ademas lo voy a trabajar con los alumnos de la academia de Jovenes Talento Matematico de la ciudad de Leon Nicaragua.
    Lo visitare en Twiter y google+, para compartir el maravillosos mundo de las matematicas.

    1. Avatar de David Orden

      @30 Ernesto González: ¡Muchísimas gracias! No hay mejor recompensa para una entrada que ayudar a aprender. Por favor, cuéntenos (por aquí o por donde sea) cómo resulta la experiencia. Hay otras entradas con problemas que pueden servir para ese tipo de alumnos; si quiere alguna sugerencia no dude en preguntar. Un saludo.

  23. Avatar de AlejoAlcano
    AlejoAlcano

    Ayudame es de puntos y rectas dice que aga en una hoja lisa un punto A y B de 10cm de distancia y marquen dos puntos C,D a 3 cm de A. y B a 7cm Ayudaa… por favor espero su respuesta…..

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Sobre el autor
Fotografía del autor

Soy profesor del área de Matemática Aplicada en la Universidad de Alcalá. Me interesa aprender y ayudar a aprender. Me gusta conectar las matemáticas con otros campos. Cuento cosas en Twitter como @ordend. Tengo una página profesional con más información.

Sobre el blog

Este blog trata sobre matemáticas, miradas desde distintos puntos de vista. Pretende ser cooperativo, porque seguro que hay algo de lo que sabes más que otros y, aunque no lo hayas pensado nunca, tiene matemáticas detrás. Queremos pasarlo bien jugando a pensar y ayudarnos entre todos a aprender cosas. Puedes seguir a @cifrasyteclas en Twitter o visitarnos en Facebook.

Entradas recientes
Comentarios recientes
  1. Hola, cualquier número (que no sea 0) elevado a la 0 da 1. Saludos

  2. Muy interesantes explicaciones, tanto para 0! como para nº(exponente 0). El tema se me ha actualizado a razón de algunas…

FIltro
Nube de etiquetas

Acertijo Alumnos Carnaval de Matemáticas Charla Ciencia Circunferencia Coches Concurso Conducir Cruces decimal Divulgación Erdős Estudiantes Gala Geometría Computacional Grafo Gráfica Guadalajara Imagen Ingeniería Investigación Juego Madrid Malla Matemáticas Motor Naturales Número Números Pi Plano Premios Primos Probabilidad Problema Problemas abiertos Puntos Segmentos Suma Teoría de números Triángulo Universidad Universidad de Alcalá Utiliza matemáticas