Dentro de los pasatiempos dinámicos se engloban aquellos que consisten en hallar la serie de movimientos necesaria para resolver cierta tarea. De entre estos, los problemas relativos recorridos en tableros de ajedrez (algunas de las cuales son modelizables mediante grafos) y los de cruces de ríos son algunos de los más conocidos. También son famosos el juego del 15, las torres de Hanoi y los anillos chinos (ver Ball y Coxeter, páginas 312-323, y Dewney, página 194).
Problema: En la siguiente figura
invertir las posiciones de los caballos blancos y negros, en un número mínimo de jugadas.
Problema: En un tablero 4´3, con tres caballos blancos situados en las 3 casillas superiores y 3 negros en las 3 casillas inferiores, intercambiar las posiciones de los caballos blancos con las de los negros, en un número mínimo de jugadas.
Dentro de los juegos que podríamos considerar de combinatoria, uno de los acertijos más viejos es el del granjero que viaja con un lobo, un cordero y una cesta de repollos. Por razones obvias no puede dejar solos en ningún momento al lobo y al cordero, ni al cordero y los repollos. En un momento dado llegan a un río. Para cruzarlo tiene un bote en el que solamente puede cruzar él con uno de los tres "objetos".
Problema: ¿Cómo hará para cruzar el río?
Problema: Una variante también clásica es la de los tres hombres y los tres niños con la restricción de que el bote únicamente permite cruzar a un hombre o dos niños cada vez. ¿Cómo harán para cruzar el río?
Problema: ¿Cuántas travesías habrían sido necesarias si solamente hubiera habido dos niños? ¿En este ultimo caso, ¿cuántas travesías serían necesarias para cruzar un regimiento de 1000 soldados?
Problema: Una última variante es las dos (o tres) parejas en las que los maridos son tan celosos que no permiten a su mujer estar con otro hombre, aunque haya más personas presentes, si no están ellos presentes. ¿Sabrías resolver esta última variante?
Problema: ¿Estúdiese el caso de cuatro (o más) parejas?
Otra familia clásicas de problemas tiene por protagonistas trenes y cambios de agujas.
Problema: En la figura está representada una vía principal (horizontal), junto con dos ramales secundarios curvos. El rectángulo mayor situado en la vía principal representa una máquina. Los dos rectángulos menores representan vagones.
El extremo común A de los ramales no puede ser utilizado por la máquina, aunque sí por cualquiera de los vagones (aunque no los dos a la vez). El problema consiste en utilizar la máquina para intercambiar los vagones, dejando la máquina en su misma posición inicial. La máquina puede enganchar los vagones tanto delante como detrás. Además un vagón puede engancharse con el otro.
Problema: El problema es ahora el mismo pero en la siguiente figura.
Ahora B solo puede albergar la máquina y un vagón, mientras que C únicamente puede ser utilizado por uno de los vagones.
Problema: El problema consiste ahora en permitir el cruce de dos trenes, uno que viene de la izquierda y otro que viene de la derecha, con 40 vagones cada uno, si el ramal auxiliar únicamente puede alojar únicamente 40 vagones o una máquina y 39 vagones.
Problema: Un nuevo tren con 40 vagones y un furgón de cola quiere utilizar el ramal anterior para cambiar de sentido. El orden de los vagones se puede alterar en la maniobra, aunque ha de terminar con la locomotora en la parte delantera y el furgón de cola en último lugar. ¿Es posible hacerlo?
Problema: Uno de los juegos con monedas más antiguos consiste en colocar en fila 8 monedas, y tratar de agruparlas, en 4 movimientos, en 4 montones de 2 monedas cada uno. En cada movimiento cada moneda debe saltar exactamente sobre otras dos (independientes o apiladas).
Problema: ¿Puede resolverse el problema anterior con 10 monedas en 5 movimientos? ¿Y 12 en 6 movimientos? ¿Hay alguna estrategia general para 2n monedas en n movimientos?
Problema: Obtener, para 10 monedas un método de apilamiento en el que los montones de 2 monedas resultantes al final sean equidistantes.
Problema: ¿Podrías conseguir que las monedas terminaran en los lugares impares?
Problema: Otro juego consiste en colocar, alternadas, 8 monedas de dos tipos distintos (4 de cada tipo), dejando sitio en un extremo para poner 2 monedas más. Tras 4 movimientos, las monedas de cada han de estar alineadas, en 2 grupos separados. En cada movimiento hay que mover juntas dos monedas adyacentes a otro lado.
A principios de siglo fue comercializado el siguiente juego, consistente en un caja de madera con 15 bloques que podían ser deslizados por la caja (sin sacarlos de ella). Los bloques venían en la posición inicial
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 15 | 14 |
El puzzle consistía en llevarlos a su posición natural
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 |
Por ejemplo, a partir de la posición inicial, tras realizar un único movimiento, podemos obtener únicamente 2 posiciones,
| 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | |
| 5 | 6 | 7 | 8 | 5 | 6 | 7 | 8 | |
| 9 | 10 | 11 | 12 | 9 | 10 | 11 | ||
| 13 | 14 | 15 | 13 | 14 | 15 | 12 |
Y a partir de éstas (si no retrocedemos),
| 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | |||
| 5 | 6 | 7 | 8 | 5 | 6 | 7 | 8 | 5 | 6 | 7 | 5 | 6 | 7 | 8 | ||||
| 9 | 10 | 11 | 12 | 9 | 10 | 12 | 9 | 10 | 11 | 8 | 9 | 10 | 11 | |||||
| 13 | 14 | 15 | 13 | 14 | 11 | 15 | 13 | 14 | 15 | 12 | 13 | 14 | 15 | 12 |
El inventor del puzzle, Sam Loyd, ofreció 1000 dólares (de 1900) a quien lo resolviera. Miles de personas aseguraban haberlo resuelto, pero lamentablemente no recordaban los movimientos que habían realizado. No es de extrañar puesto que el puzzle no tiene solución.
Problema: Intenta justificar esta última afirmación.
Un problema, quizás no tan viejo, pero sí sencillo, se refiere a esos calendarios formados por dos cubos con números en sus caras con los cuales es posible construir cualquier fecha del mes. ¿Sabrías determinar los números que han de aparecer en cada uno de los dados?
El problema consiste en trasladar la pila a otra varilla, moviendo un disco cada vez, de manera que en ningún momento un disco descanse sobre otro de menor tamaño. Inicialmente sólo es posible mover el disco de menor tamaño. El segundo movimiento también está forzado. A partir del tercer movimiento, la elección ya no es única.
Problema: Busca la serie de movimientos para los problemas de 2, 3 y 4 discos.
El análisis de estos primeros casos acerca rápidamente a la clave de la solución. Si se puede mover la torre formada por los cuatro discos superiores, ¿por qué no va a poder moverse toda la torre? ¿Cómo puedo aprovechar la manera en que se mueven 4 discos, para intentar mover 5? ¿Y si consigo mover 5, como podré mover 6?Problema: ¿Cómo se puede aprovechar la estrategia de movimiento de k discos, para mover k+1?
La solución de este ejercicio nos proporciona una solución recurrente, que nos permitirá obtener, a partir de la estrategia para k discos, la estrategia para k+1.
Problema: Utilizar la relación de recurrencia anterior para determinar el número de movimientos necesarios para trasladar n discos.
Problema: Considera nuevamente los casos de 2,3 y 4 discos. En cada uno de ellos intenta contestar a las siguientes preguntas:
Problema: Quizás hayas observado más pautas en la obtención de la estrategia general.
Un hombre que viajaba un montón estaba preocupado
por la posibilidad de que hubiera una bomba en alguno de los aviones en que
viajaba. Determinó la probabilidad de que ocurriera esto y aunque
era baja no lo era tanto como hubiera deseado. Desde entonces viaja siempre
con una bomba en su maleta. Piensa que la probabilidad de que haya dos
bombas a bordo debe ser ahora despreciable.
Razonamientos como el anterior son comunes. Este hecho hace que a veces sea
sorprendente el resultado real de algunos razonamientos sobre probabilidades.
Uno estos resultados a primera vista sorprendente surge de la siguiente pregunta (es interesante responder primero rápidamente, sin efectuar grandes cálculos, y dar después una respuesta más meditada).
Problema: ¿Cuánta gente estimas que debería haber en una habitación para tener ½ de probabilidad de que haya la menos dos personas con el mismo cumpleaños?
Un posible contraataque de un escéptico es el siguiente: "Muy bien, listillo, te voy a demostrar que estas equivocado. ¿A ver cuanta gente hay aquí? Unas 100 personas. A ver, mi cumpleaños es el 28 de Febrero. ¿Alguno de ustedes cumple años también ese día? Ves, ninguno.
Pregunta 2: ¿Qué falla en este razonamiento?
La moraleja de esto es que el que ocurra un suceso improbable cualquiera es mucho más probable que el que ocurra un suceso improbable en particular. Que me toque la lotería es muchísimo más improbable a que le toque a alguien. De hecho, siempre que se vendan todos los décimos, la probabilidad de esto último es 1.Problema: Supongamos que dispongo de tres cartas. Una de ellas tiene un as de oros en cada lado, otra un as de copas en cada lado y la tercera un as de oros en un lado y un as de copas en el otro. Echa las tres cartas en un sombrero y extrae una al azar. Supongamos que en la cara visible tiene un as de oros. Por tanto solamente puede ser la carta que tiene un as de oros en cada lado, o la que tiene un as de oros en un lado y un as de copas en el otro. Por tanto la probabilidad de que las dos caras sean iguales es, aparentemente, igual a la de que las dos caras sean diferentes. Si me apuesto entonces algo a que son iguales no te estoy timando. ¿O sí?
Problema: Ahora dispongo de tres medias nueces y de una canica, que escondo debajo de una de las tres nueces. Intenta adivinar debajo de qué nuez la he puesto. Una vez que has elegido una de las nueces destapo una de las otras dos que no esconda la canica. Llegado este punto, hay dos nueces boca abajo, una de las cuales esconde la canica. Por tanto, de nuevo aparentemente, la probabilidad de que estés señalando la nuez que esconde la canica es ½. Si me apuesto entonces algo a que no has acertado es una apuesta justa. ¿O te estoy timando otra vez?
Problema: Visto esto, ¿cuál será la estrategia que habrás de seguir si alguna vez te encuentras en el lugar de la víctima?
El último timo que presentaré y en que también es fácil caer es el siguiente. Es un juego que se juega en los casinos de Estados Unidos y en los pubs ingleses al grito de tres ganan y tres pierden.
El juego consiste en lanzar tres dados, debiendo acertar uno de los que van a salir. En ese caso recibes tu apuesta tantas veces como haya salido ese número. Si no, la pierdes.
Si se tirara únicamente un dado el número que has elegido saldría una de cada seis veces, si se tiraran dos dados ese mismo número saldría una de cada seis veces: Como se tiran tres dados saldrá una de cada dos veces. Así que estas a la par. Incluso se diría que tienes las de ganar porque una de cada dos partidas saldrá el número que has elegido y cubrirás pérdidas. Pero si además el número sale en dos dados empezarás a ganar dinero.
Pregunta 6: ¿Juegas entonces?
Problema: Supongamos que lanzo tres monedas al aire. Si salen todas
iguales te pagaré, digamos, 100 ptas; pero si no son todas
iguales tendrás que pagarme 50 ptas.
De las tres monedas
dos habrán de ser necesariamente iguales. La tercera podrá ser
igual o diferente que esas dos. La probabilidad de ambos casos
son iguales. Por tanto en una de cada dos tiradas las tres
monedas serán iguales. Como en caso de ser iguales ganas el
doble de lo que pierdes si son distintas el juego te favorece.
¿Estás de acuerdo y juegas?
Problema: Tres tiradores A,B y C acuerdan batirse en un duelo triangular con las siguientes reglas: Situados en los vértices de un triángulo equilátero y después de acordar el orden, dispararán por turno un disparo a aquel de los otros dos que prefiera. El duelo continuará en este orden hasta que únicamente quede uno de los duelistas. Se sabe que A acierta siempre, B un 80% y C un 50%. Suponiendo que todos escogen la mejor estrategia y que nadie resulta herido por un disparo no dirigido a él, ¿quién tiene más probabilidades de sobrevivir?
Pregunta 7: ¿Sabrías calcular la forma en que es de esperar que se desarrolle el juego para uno cualquiera de los jugadores (esperemos que no seas tú uno de ellos) a lo largo de un número adecuado de partidas?
Problema: Tengo un amigo que tiene un hermano mellizo. ¿Cuál es la probabilidad de que sea un chico? ¿Y si sabemos además que su hermano mellizo es menor que él?
Problema: Fulanito, que vive en Aluche, tiene dos novias: una en Alcorcón y otra en Atocha. Como nunca sabe con cuál de las dos quedar, ha llegado al siguiente convenio consigo mismo. Como los trenes a Atocha y Alcorcón pasan cada 20 minutos cogerá el primer tren que pasa, dejando así que los trenes decidan por él. Después de un tiempo, su novia de Atocha, que está locamente enamorada se ha empezado a quejar de que solamente va a verla un día de cada cuatro. Por otra parte, su novia de Alcorcón, que ya está empezando a estar harta de él, se queja de que va a verla 3 de cada 4 días. Aparte de ser un cretino, ¿cuál es el problema de Fulanito?
Problema: Supongamos que te has hecho una prueba, para una cierta enfermedad, que tiene una fiabilidad del 98%, esto es, si alguien tiene esa enfermedad, la prueba dará resultado positivo el 98% de los casos, mientras que si no la tiene, será negativo el 98% de los casos. Supongamos también que 1 de cada 200 personas que se realizan la prueba realmente padece la enfermedad. Supongamos finalmente que te has hecho la prueba y ha dado positivo. ¿Cómo de preocupado (o preocupada) deberías estar?
Problema: El entrenador del equipo de baloncesto de mi pueblo está dudando entre dos fichajes para esta temporada, llamémosles A y B. Tanto en la primera mitad de la temporada pasada, como en la segunda mitad, A ha tenido un mejor porcentaje de canastas por partido jugado que B. Como además, el fichaje de A es ligeramente (100 millones) más barato que el de B, parece que el entrenador lo tiene claro. Aún así me ha pedido consejo. ¿Qué consejo le darías tú?
Problema: El siguiente problema está íntimamente relacionado con el anterior. Supongamos que se tiene la siguiente relación entre dos caballos de carreras: Para cada tiempo t, es más probable que el caballo A cubra la distancia de la carrera en un tiempo inferior a t a que lo haga el caballo B. ¿Se deduce de esto que en una carrera es más probable que el caballo A gane al caballo B?
Supón que durante los 6 últimos meses has recibido una carta de una agencia bursátil anticipándote la tendencia (al alza o la baja) de determinadas acciones, habiendo acertado siempre. Acabas de recibir una carta de la misma agencia en la que se te pide la cantidad de 15.000 pesetas para seguir recibiendo información. Aparentemente, los tipos de esta agencia son unos fieras y aciertan siempre (la probabilidad de acertar 6 veces seguidas al azar es de 1 entre 46.656), con lo que sería altamente provechoso seguir disponiendo de información. Así por fin podrías hacer algo con esos ahorrillos que tenemos en el banco y que te producen un miserable 8% anual. ¿Aceptas entonces y les envías las 15.000 pesetas?
Mejor no lo hagas no sea que pierdas las 15.000 pesetas y también tus ahorros.
Pregunta 13: ¿De que manera es posible para alguien sin la menor idea sobre la Bolsa enviarte 6 predicciones exactas?
Los problemas de esta sección difieren de los de la anterior en que, mientras que aquellos admitían soluciones, aunque sorprendentes, eran correctas, los de esta sección, salvo el primero, no admiten una solución que esté comúnmente aceptada.
Supongamos que tenemos tres candidatos a la presidencia A, b y C. Una encuesta indica que 2/3 del electorado prefieren a A antes que a B, y que 2/3 del electorado prefieren a B antes que a C. ¿se deduce de esto que la mayoría de votantes prefiere a A antes que a C?
Problema: Diseñar tres grupos de población (de igual tamaño), de tal forma que los individuos de cada grupo comparten las mismas preferencias electorales, de forma que se cumplan los porcentajes anteriores, pero también se cumpla que 2/3 del electorado prefieren a C antes que A.
Este es un ejemplo de que la relación de preferencia 2 a 2 no es transitiva. Esta paradoja se conoce como la paradoja de Arrow, en recuerdo de Kenneth J. Arrow, premio Nobel de Economía, quien demostró a partir de ella y de otras consideraciones lógicas que un sistema perfecto de votación democrática es, en principio, imposible.
Problema: Supongamos que en otra elección, tanto el candidato A como el B cuentan cada uno con más del 40% de los votos (y por tanto C cuenta con menos del 20%). Supongamos que la elección se realiza enfrentando primero 2 candidatos, y después el vencedor con el tercero. ¿Es posible que gane C?
Problema: Supongamos ahora que, entre 4 partidos políticos A, B, C y D las preferencias se reparten como sigue:
Determínese un orden de votación según la cual resulte ganadora la opción C.
Problema: Demuéstrese que cualquiera de los partidos puede resultar vencedor, eligiendo convenientemente el orden de los enfrentamientos.
Problema: ¿Es posible que, determinando únicamente el primer enfrentamiento, gane C, independientemente de los enfrentamientos posteriores?
Supongamos que se lanza una moneda. Si sale cara te pago 1 peseta. Si sale cruz se vuelve a lanzar la moneda. Si sale cara ahora te pago 2 pesetas. En caso contrario se vuelve a lanzar la moneda y si sale cara te pago 4 pesetas. En caso contrario se sigue lanzando la moneda hasta que salga cara. Tu ganancia será n pesetas, siendo n+1 el número de tiradas que has necesitado para obtener cara.
La pregunta es, ¿cuánto debería cobrarte para dejarte jugar?
Si por ejemplo, juegas 16 partidas:
Así, en 16 partidas es de esperar que ganes
más de 8·1+4·2+2·4+1·8=32 pesetas, con una ganancia media superior
a 32/16=2 pesetas.
Pero si juegas 32 partidas:
Así, en 32 partidas es de esperar que ganes
más de 16·1+8·2+4·4+2·8+1·16=5·16 pesetas, con una ganancia media
superior a 2.5 pesetas.
Es fácil ver que, conforme aumenta el
número de partidas que juegas, la ganancia media aumenta de forma
que si juegas 2n partidas, es de esperar que ganes más
de n/2 pesetas.
Cómo, inicialmente puedes jugar tantas partidas cómo quieras,
tenemos que la ganancia que puedes esperar es infinita.
Calculado más directamente, cómo tenemos
la siguiente tabla de probabilidades y ganancias,
| Ganancia | 1 | 2 | 4 | 8 | 16 | 32 | .. |
| Probabilidad | ½ | 1/4 | 1/8 | 1/16 | 1/32 | 1/64 | .. |
la ganancia a esperar será de
. Esto es, para jugar deberías pagar una cantidad infinita de pesetas.
Entre las diferentes maneras propuestas para hacer la probabilidad finita, una es la propuesta por Cramer (en una carta a Nicolas Bernouilli) en 1730. Cramer supuso que la fortuna del banquero es finita (por ejemplo 224 pesetas). En este caso, el jugador recibirá 2n pesetas con probabilidad 1/2(n+1), siempre que n sea menor o igual que 24. En el resto de los casos recibirá siempre 224 pesetas. Como
,
la ganancia esperada es ahora únicamente de 13 pesetas, una suma razonable.
El juego que proponemos ahora es el
siguiente: Dos personas apuestan sobre la cantidad de dinero que llevan
encima. Aquel que lleve menos dinero gana todo el dinero del otro.
Cada uno de los dos apostantes razona de la siguiente manera: "Si yo
tuviera más dinero perdería todo el dinero que llevo, pero si soy el
que menos dinero lleva de los dos, ganaré más dinero del que llevo. Es
decir, lo que puedo perder es menos de lo que puedo ganar. ¡El juego me
favorece!"
Pero este razonamiento se lo hacen los dos jugadores.
¿Cómo es posible que el juego sea favorable a los dos jugadores?
El razonamiento de Pascal para ser cristiano aparece en el Pensamiento 233 de sus Pensées: Nadie puede decidir inequívocamente si debe aceptar o rechazar la doctrina de la Iglesia Católica. Puede ser verdadera o falsa. Independientemente de las probabilidades de cada una de estas 2 posibilidades, ¿cuáles son los beneficios de ambas elecciones?
Por tanto, la balanza de ganancias y pérdidas se inclina a favor de la Iglesia. ¿Estás de acuerdo?
William James, en su ensayo The will to believe aducía que la decisión de creer en Dios es para nosotros una buena apuesta, porque al no haber pruebas ni en un sentido ni en otro, respecto a la existencia de Dios, uno debería decidir aquello que más feliz pueda hacerle en esta vida.