Cuatro sospechosos

.



por Adrián Paenza

El siguiente problema tiene una particularidad. En apariencia, parece un acertijo. Me resisto a escribir “problemas de ingenio”. Lo que suele pasar con ellos es que si a uno se le ocurre lo que hay que hacer, bárbaro. Pero si no, genera una frustración que invita a no querer pensar más.

En cambio, el problema que sigue tiene lógica. Tiene una lógica impecable. Puede que no sea sencillo, pero inexorablemente, si uno se dedica a pensarlo, seguro que lo resuelve. Podrá no disponer del tiempo o de las ganas de hacerlo, pero de lo que no me quedan dudas es de que presenta un desafío que cualquier persona puede hacer. Aquí va.

Se denunció un robo de dinero y la policía detuvo a cuatro sospechosos. Los cuatro fueron interrogados, y se sabe que uno sólo dijo la verdad. El problema consiste en leer lo que dijo cada uno, y encontrar razones que demuestren quién fue el que dijo la verdad, o sea, encontrar al único que no mintió.

El sospechoso número 1 dijo que él no robó el dinero.

El sospechoso número 2 dijo que el número uno mentía.

El sospechoso número 3 dijo que el número dos mentía.

El sospechoso número 4 dijo que el número dos fue quien robó el dinero.

Si yo fuera usted, aquí haría una pausa. Me sentaría un rato con un papel, una lapicera, y ganas de disfrutar pensando. Yo voy a escribir las distintas posibilidades a partir del párrafo siguiente, pero hágame caso, no lea lo que sigue. Hágalo usted. Lo va a disfrutar más. Lo que voy a hacer ahora es analizar lo que dijo cada uno de ellos, suponiendo que dijo la verdad. Y ver a qué conclusiones o contradicciones me lleva.

A partir de ahora, por comodidad, a los sospechosos los voy a llamar directamente Nº 1, Nº 2, Nº 3 y Nº 4.

1) Si Nº 1 fuera el que dijo la verdad, esto implica que Nº 1 NO FUE el que robó el dinero (porque él está diciendo la verdad). En ese caso, no hay problemas en aceptar que Nº 2 NO dice la verdad. Está mintiendo cuando dice que Nº 1 es el que mentía. Luego, no hay problemas allí. Pero SI hay problemas con la afirmación de Nº 3. Porque si él –el número 3– miente (y tiene que mentir porque estamos suponiendo que Nº 1 es el UNICO que dijo la verdad), entonces, sería MENTIRA lo que dijo él, o sea, que sería mentira que Nº 2 mentía..., o sea, Nº 2 decía la verdad..., pero en ese caso sería cierto que Nº 1 mentía. Pero si Nº 1 mentía, entonces cuando él dice que NO robó el dinero estaría mintiendo. Y eso implicaría que fue EL el que robó el dinero. Y ESO CONTRADICE que estamos suponiendo que Nº 1 es el único que está diciendo la verdad. Este caso, NO puede ser posible.

2) Si Nº 2 fuera el UNICO que dice la verdad, entonces Nº 1 estaría mintiendo..., eso implica que fue EL quien robó el dinero. Entonces, hasta ahí vamos bien. Se concluye hasta aquí que Nº 1 fue quien robó el dinero. Por otro lado, como Nº 3 miente, entonces, no hay problemas de contradicción alguna, porque SABEMOS que Nº 2 dice la verdad, por lo que lo que está diciendo Nº 3 es mentira. Y el número 4, si fuera también mentira lo que dijo, entonces, eso querría decir que Nº 2 NO robó el dinero. Y eso tampoco contradice nada. Es decir, SUPONER QUE FUE Nº 2 EL UNICO QUE DICE LA VERDAD no ofrece contradicciones con el resto de las afirmaciones.

3) Si Nº 3 fuera el UNICO que dice la verdad, entonces, eso significaría que Nº 2 miente. Pero si Nº 2 miente, entonces eso quiere decir que Nº 1 decía la verdad. Pero si Nº 1 dice la verdad, entonces él no robó el dinero. Pero en ese caso, lo que dice el Nº 1 TAMBIEN sería cierto. Eso CONTRADICE que Nº 3 fuera el UNICO que está diciendo la verdad. Este caso no puede ser posible.

4) Si Nº 4 fuera el UNICO que dijo la verdad, entonces eso implicaría que Nº 2 fue quien robó el dinero. Pero, como OBLIGADAMENTE Nº 3 miente, eso querría decir que lo que dijo es falso, y por lo tanto, Nº 2 estaría diciendo la verdad. Y lo que dijo Nº 2 fue que Nº 1 mentía. Pero si Nº 1 mentía, entonces, ¡¡¡fue Nº 1 quien robó el dinero!!!. Y eso contradice que fue Nº 2 quien robó el dinero.

Moraleja 1: la única manera de que UNO sólo de ellos hubiera dicho la verdad y no se PRODUZCAN CONTRADICCIONES es que haya sido Nº 2 el UNICO que dijera la verdad.

Moraleja 2: este tipo de problemas, más allá de ser entretenidos o no, nos entrenan para poder tomar decisiones que aparecen como complicadas. Muchas veces en la vida, uno tiene que analizar distintos tipos de escenarios y cuando advierte que hay muchas variables, la pereza lo inunda y prefiere claudicar. Por eso, más allá del valor lúdico que tienen, enseñan a pensar. Y ayudan a elegir. Ah, y aunque no lo parezca (una vez más), también es hacer matemática.

Diario Página12 24/12/2006.-




.

Problema del Viajante de Comercio

.



por Adrián Paenza

Si usted fuera capaz de resolver el problema que voy a plantear ahora, podría agregar un millón de dólares a su cuenta bancaria. Eso es la que está dispuesto a pagar el Clay Mathematics Institute.

El problema es de enunciado realmente muy sencillo y se entiende sin dificultades. Claro, eso no quiere decir que sea fácil de resolver, ni mucho menos.

De hecho, usted verá que si sigue leyendo pondrá en duda varias veces que a alguien le puedan pagar semejante suma por resolver lo que parece ser una verdadera pavada. Sin embargo, hace más de 50 años que está planteado y, hasta ahora, nadie le encontró la vuelta. Acompáñeme. Una persona tiene que recorrer un cierto número de ciudades que están todas interconectadas (pueden ser rutas, carreteras o por avión). Es decir, siempre se puede ir de una hacia otra en cualquier dirección.

Además, otro dato que se tiene, es cuánto sale ir de una a otra. A los efectos prácticos, vamos a suponer que viajar desde la ciudad A hasta la ciudad B, sale lo mismo que viajar desde B hasta A.

El problema consiste en construir un itinerario que pase por todas las ciudades una sola vez, y que termine en el mismo lugar inicial, pero con la particularidad que sea el más barato. ¡Eso es todo! No me diga que no le dan ganas de volver para atrás y leer de nuevo, porque estoy seguro que a esta altura, usted debe dudar de que entendió correctamente el enunciado del problema. Una de dos: o usted no entendió bien el planteo o hay algo que anda mal en este mundo. Sin embargo, está todo bien sólo que la dificultad aparece escondida. Los intentos que distintas generaciones de matemáticos han hecho tratando de resolverlo han permitido múltiples avances, sobre todo en el área de optimización, pero hasta ahora, mayo de 2006, el problema general no tiene solución.

Yo sé que en este momento usted duda de mí, duda de usted... duda de todo. Tiene que haber algo que esté mal. Sigamos.

Hagamos algunos ejemplos sencillos, con pocas ciudades.

Para dos ciudades, dos caminos:

ABA y BAB

Para tres ciudades, seis caminos:

ABCA BACB CABC

ACBA BCAB CBAC

Para cuatro ciudades, veinticuatro caminos:

ABCDA BCDAB CABDC DABCD

ABDCA BCADB CADBC DACBD

ACBDA BDACB CBADC DBACD

ACDBA BDCAB CBDAC DBCAD

ADBCA BACDB CDABC DCABD

ADCBA BADCB CDBAC DCBAD

Supongamos ahora que en lugar de cuatro ciudades, hubiera cinco.

¿Cuántos caminos posibles habrá? (y acá estará la clave).

¿En cuántas ciudades se puede empezar el recorrido? Respuesta: en cualquiera de las cinco (A, B, C, D y E).

Una vez elegida la primera, ¿cuántas posibilidades quedan para la segunda ciudad? Respuesta: cualquiera de las cuatro restantes. O sea, nada más que para recorrer las primeras dos ciudades hay ya veinte posibles maneras de empezar:

AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC y ED.

¿Y ahora? ¿Cuántas posibilidades hay para la tercera ciudad? Como ya elegimos dos, nos quedan tres para elegir. Luego, como ya teníamos veinte maneras de empezar, y cada una de éstas puede seguir de tres formas, con tres ciudades, entonces ahora tenemos 60 (sesenta) formas de empezar con tres ciudades. (¿Advierte ya en dónde empieza a estar la dificultad?) Sigo.

Para la cuarta ciudad a elegir, ¿cuántas posibilidades quedan?

Respuesta: dos (ya que son solamente dos las ciudades que no hemos utilizado en el itinerario que hicimos hasta ahora). Luego, para cada una de las 60 formas que teníamos de empezar con tres ciudades, podemos continuar con dos ciudades. Luego, tenemos 120 itinerarios con cuatro ciudades.

Y ahora, para el final, no nos queda nada para elegir, porque de las cinco ciudades que había, ya hemos seleccionado cuatro: la quinta queda elegida por descarte, es la única que queda.

Moraleja: tenemos 120 itinerarios.

Si usted relee lo que escribimos recién, al número 120 llegamos multiplicando los primeros cinco números naturales:

120 = 5 x 4 x 3 x 2 x 1

Este número se conoce con el nombre 5!, pero no es que se lea con gran admiración, sino que los matemáticos llamamos a este número el factorial de cinco. En el caso que estamos analizando, el número cinco es justamente el número de ciudades. (*)

Es fácil imaginar lo que va a pasar si en lugar de tener cinco ciudades, se tienen seis. El número de caminos posibles será:

6! = 6 x 5 x 4 x 3 x 2 x 1 = 720

Sigo un par de pasos más.

Siete ciudades, 7! = 5040 posibles caminos

Ocho ciudades, 8! = 40.320 caminos

Nueve ciudades, 9! = 362.880 caminos

Diez ciudades, 10! = 3.628.800 caminos

Y paro acá. Como usted se da cuenta, el total de rutas posibles que habría que analizar con sólo diez ciudades es de ¡más de tres millones seiscientos mil!

La primera conclusión que uno saca es que el factorial de un número aumenta muy rápidamente a medida que uno va avanzando en el mundo de los números naturales. Tan rápido aumenta, que lo invito a que usted haga las cuentas para convencerse.

Imagine que ahora usted es un viajante de comercio y necesita decidir cómo hacer para recorrer las capitales de las 23 provincias argentinas, de manera tal que el costo sea el menor posible. O sea, de acuerdo con lo que vimos recién, habría que analizar

25,852,016,738,885,000,000,000

rutas posibles (más de ¡veinticinco mil trillones!).

Por lo tanto, se advierte que para resolver el problema hace falta tener una computadora ciertamente muy potente. Pero aun así, este ejemplo (el de las 23 capitales) es muy pequeño.

Creo que ahora queda clara la dificultad. No reside en hacer las cuentas ni en el método que hay que emplear. ¡Esa es la parte fácil! Es que hay que sumar el costo de recorrer cada camino y luego comparar. Al final, uno se queda con el más barato y listo. Pero el problema, insalvable por ahora, es que hay que hacerlo con muchísimos números, un número enorme, que aun en los casos más sencillos, de pocas ciudades, parece inabordable. Lo que se intenta hoy es tratar de encontrar alguna manera de encontrar la ruta más barata sin tener que hacer todos los cálculos, sumar y luego comparar. Ya con 100 ciudades, se sabe que el número de itinerarios posibles es tan grande, que ni siquiera las computadoras más poderosas pueden manejarlo. Hay varios casos particulares que fueron resueltos, pero en esencia, el problema está abierto.

Un último comentario: con los actuales modelos de computación, el problema no parece que tenga solución. Hará falta entonces, que aparezca alguna nueva idea que revolucione todo lo conocido hasta acá.

Diario Página12 18/6/2006.-



.