sábado, 30 de abril de 2011

País de palillos

Enunciado

Estos problemas sobre estrategias de juegos son muy habituales entre los aficionados a los problemas de ingenio, aunque tienen muchos enfoques diferentes.

En el primer juego, lo importante es el número total de palillos que quedan sobre la mesa, ya que si es múltiplo de 4, el que juega está en una posición perdedora. De esta forma, como al principio hay 19 palillos, basta quitar 3 y dejar a nuestro rival con una posición perdedora.

Cuando el juegue, dejará 15, 14 o 13, y nosotros trataremos de quitar, respectivamente, 3, 2 o 1 palillos, hasta 12. Repetiremos la jugada, sumando 4 con nuestro rival, hasta que queden 4, ya que él no puede terminar, pero nosotros sí, en cuanto el retire alguno de los palillos sobrantes. Es una estrategia ganadora para el que empieza.

La forma ideal de encontrar esta estrategia consiste en empezar a estudiar el caso con muy pocos palillos, hasta descubrir los números que forman una posición ganadora o perdedora.

El segundo juego es ligeramente distinto, ya que es un juego del tipo del famoso NIM. Sin embargo, la estrategia en este juego se simplifica, ya que el número de palillos por letra es 5 - 5 - 4 - 5, y para equilibrar la partida basta quitar un palillo, por ejemplo, a la letra A, dejando 5 - 4 - 4 - 5. A partir de ahí, repetiremos las jugadas de nuestro adversario, tratando de que lo que él haga en la I, lo repetiremos en la A y viceversa, y lo que haga en la S lo repetiremos en la P y viceversa. Por ejemplo, si quita tres palillos a la s, nosotros quitamos tres palillos a la P. Al final, llegaremos a un punto en que no quedarán más que dos letras con la misma cantidad de palillos cada una, incluso puede que sólo un palillo cada una. Si hace desaparecer una letra, nosotros podemos acabar con la última. Por tanto, tenemos, como antes, una estrategia ganadora para el que empieza.

Un caso más general es más complejo, porque la estrategia conocida (y creo que única) consiste en descomponer las cantidades en suma de potencias de 2, y tratar de que todas las potencias de 2 aparezcan siempre un número par de veces.

jueves, 28 de abril de 2011

Alienígenas maripósidos

Enunciado

Este ha sido uno de los problemas qué más he disfrutado escribiendo. Se basa en otro que leí hace tiempo, y quería ponerle nombres divertidos.

La clave es que la transformación de estos tipos de alienígenas converge, ya que su número no varía. Dejemos de momento su convergencia, y estudiemos primero su punto de equilibrio.

Si en algún momento se quedan sin variación ¿qué cantidades habrá de cada uno? Llamemos a esas cantidades X gusánidos, Y maripósidos y Z jiráfidos. En ese caso, después de una semana, el número de gusánidos será 0.3X + 0.25Z = X, además 0.9Y + 0.7X = Y y 0.75Z + 0.1Y = Z. Sin embargo, estas tres relaciones son dependientes, es decir, una de ellas depende de las otras dos, como es fácil comprobar. Nos falta, por tanto, añadir que X + Y + Z = 1080, que es la relación clave. A partir de ahí, podemos averiguar los valores de estabilidad.

De la primera igualdad, obtenemos que 30X + 25Z = 100X, por lo que Z = 70X/25. De la segunda igualdad, 90Y + 70X = 100Y, obtenemos que Y = 7X. Substituyendo en la última igualdad, X + 7X + 70X/25 = 1080, por lo que 25X + 175X + 70X = 27000, es decir, 270X = 27000, de donde X = 100, por lo que Y = 700 y Z = 280.

Ahora que ya tenemos las cifras de equilibrio, podemos comprobar que se aproxima más y más cada semana a estas cifras. Puesto que hemos partido de tener todo gusánidos, supondremos que a lo largo de todo el proceso cada vez tenemos menos gusánidos y más de los otros tipos. En principio, la primera semana tendremos 324 gusánidos y 756 maripósidos (y 0 jiráfidos). Si estudiamos lo que sucede las primeras semanas, vemos que hay un pequeño caos al principio, pero luego parece que converge rápidamente. Las cantidades de las primeras semanas son las siguientes : en la segunda semana, (97, 907, 76), en la tercera, 48, 885 y 147 y en la cuarta 51, 830 y 199. Veamos si a partir de aquí podemos concretar la convergencia (en realidad, a partir de la semana 14 se alcanza de manera sencilla).

Para confirmar que está más próximo al objetivo, deberíamos usar tres variables nuevas, que serían sus diferencias con el objetivo, que serían las que podemos comprobar que se hacen menores.

Supongamos que escribimos el número de gusánidos como 100 + a, el de maripósidos como 700 + b y el de jiráfidos como 280 + c. Es fácil entender que a, b y c son números enteros y no todos tienen el mismo signo (ya que entre las tres cifras deben sumar exactamente 1080). Si fuesen 0, habríamos alcanzado una situación estable. Al cabo de una semana, aplicando las fórmulas, las tres cantidades se habrían convertido en 100 + 0.3a + 0.25c, 700 + 0.7a + 0.9b y 280 + 0.1b + 0.75c.

Las nuevas diferencias con el equilibrio serán 0.3a + 0.25c, 0.7a + 0.9b y 0.1b + 0.75c. Además, la suma de sus tres valores absolutos será menor o a lo sumo igual a la suma de los valores absolutos anteriores (|ax+by| es menor o igual que |ax| + |by|), y como no todos pueden tener el mismo signo, seguro que son inferiores.

domingo, 24 de abril de 2011

Una balanza en el zoológico

Enunciado

Algunos comentarios presuponen el uso de ecuaciones, cuando en estas edades aún no se ha generalizado el uso del álgebra, al menos en un sentido tan abstracto. El método de solución que se pretende que se siga es mantener el equilibrio entre las balanzas de una manera más o menos natural (en el fondo, es álgebra).

Sabemos, por las condiciones del problema, que un elefante equilibra a un rinoceronte y un hipopótamo, mientras que cuatro elefantes equilibran con seis rinocerontes y un hipopótamo. Ahora, hay que procurar poner sobre la balanza a dos elefantes. Si seguimos con la lógica del primer equilibrio, necesitamos poner dos rinocerontes y dos hipopótamos para equilibrar, sin embargo, necesitamos poner, según dice el problema, cuatro rinocerontes, así que habrá que cambiar a los hipopótamos por rinocerontes ¿pesan lo mismo?

Si llevamos la situación de la primera igualdad a la segunda (multiplicando la carga por cuatro), tendremos cuatro elefantes equilibrados por cuatro rinocerontes y cuatro hipopótamos, mientras que en la segunda igualdad teníamos los cuatro elefantes equilibrados con seis rinocerontes y un único hipopótamo. Es decir, que cuatro rinocerontes y cuatro hipopótamos pesan lo mismo que seis rinocerontes y un único hipopótamo, y si vamos bajando de la balanza los mismos animales, llegamos a la conclusión de que dos rinocerontes pesan lo mismo que tres hipopótamos.

Entonces, en nuestro equilibrio original (dos elefantes frente a dos rinocerontes y dos hipopótamos), tenemos que añadir dos rinocerontes en un plato, podemos hacerlo añadiendo tres hipopótamos al otro, así que pasaremos a tener dos elefantes y tres hipopótamos frente a cuatro rinocerontes y dos hipopótamos. Es evidente que sobran hipopótamos en ambas balanzas, de forma que podemos lograr equilibrio, con dos elefantes y cuatro rinocerontes, añadiendo un único hipopótamo junto a los elefantes.

viernes, 22 de abril de 2011

Dividiendo en dos un reloj

Enunciado

Hay varias formas de abordar la solución. Una de ellas sería directa, tratando de clasificar todas las formas posibles de pintar el reloj, pero resulta algo confusa. La segunda opción que se me ocurrió es más sencilla, ya que no requiere estudio de la coloración concreta.

La primera idea es que es suficiente prestar atención a uno de los seis colores, ya que si tenemos una sección en dos partes del reloj con tres rojos exactamente en una parte, habrá otros tres azules, y la otra parte tendrá la misma distribución.

Consideremos que se parte en dos en un primer momento, dejando los números del 1 al 6 en un lado y del 7 al 12 en otro.

Contemos cuántos rojos han caído en el lado del 1 al 6 (conjunto A).

Sera una cantidad entre el 0 y el 6. Si esta cantidad es 3, el problema está resuelto, pero si no lo es inclinamos ligeramente el corte hasta incluir otro número (por ejemplo, el 7) en el conjunto A, y eliminar de la selección otro (en este caso, el 1). La cantidad de rojos puede aumentar en una unidad, disminuir en una unidad, o permanecer igual.

Lentamente, podemos repetir este proceso hasta dar la vuelta al reloj con los cortes, de forma que lleguemos a tomar como conjunto A el otro lado del reloj (números del 7 al 12). Si hemos partido de una cantidad mayor que 3, ahora tendremos una cantidad menor que 3, porque tenemos el conjunto contrario, y viceversa.

Como hemos ido aumentando o disminuyendo de uno en uno la cantidad de números rojos, en algún momento habremos pasado por el número 3, y en ese momento tendremos el reloj dividido en la forma que se pedía.

jueves, 21 de abril de 2011

Dividir un cuadrado

Enunciado

Dividir un cuadrado

Dividir un cuadrado

En este problema hay que leer bien el enunciado para ver a qué se refiere. Si nos pide cuatro zonas de igual área, no es necesario que tengan la misma forma.

Para poder dibujarlas todas, lo mejor es empezar por una forma concreta, estudiar con qué otra forma se complementa, y así sucesivamente hasta completar el dibujo. Después, retrocedemos a cambiar nuestras últimas elecciones, y así repetimos el trabajo tantas veces como sea necesario.

Es conveniente eliminar giros y simetrías, evitando aquellas situaciones que se puedan volver a situar como una que ya hayamos usado antes.

En mi caso, yo empecé situando en una esquina el triángulo rectángulo 2 por 1. A partir de ahí, situé en segundo lugar otro triángulo rectángulo simétrico para rellenar el rectángulo superior, y vi que tenía tres formas de terminar el dibujo.

En segundo lugar, probé a complementar el triángulo rectángulo con un isósceles de base 2, encontrando dos formas más.

Como tercera opción, añadí al triángulo rectángulo inicial otro triángulo rectángulo que formaba 90 grados con él. Hay dos figuras más a partir de esta configuración.

Una vez hice todas estas pruebas, busqué aquellas figuras que no tuviesen ningún triángulo rectángulo en los bordes, encontrando la que servía de ejemplo en el problema, y otra más.

En total, 8 combinaciones además de la original, que aparecen en el dibujo que acompaña estas líneas.

domingo, 17 de abril de 2011

Extrayendo la verdad

Enunciado

En realidad, el truco se basa en que 26*4 = 104, y sólo tenemos 105 (es decir, una más).

La clave es separar las monedas en dos montones de 52, y compararlos. Si hay uno más pesado, a lo sumo tiene una moneda falsa, con lo que lo dividimos de nuevo en dos montones de 26. El que más pese, tendrá todas sus monedas auténticas.

Si ambos montones de 52 pesan lo mismo, es porque ambos contienen una moneda falsa, y la que ha quedado fuera también es falsa. En ese caso, procedemos de la misma forma que antes con cualquiera de los dos montones, y podemos conseguir exactamente 26 monedas auténticas.

Nota: ya he corregido la respuesta, gracias por el comentario.

viernes, 15 de abril de 2011

Cuadrado mágico de productos

Enunciado

Basta plantear en este ejercicio claramente las condiciones que se desean, por ejemplo, tendríamos 9 incógnitas (los contenidos de las celdas y el producto) y ocho relaciones, que corresponderían a todas las igualdades.

En realidad, bastan unas pocas de estas igualdades para darse cuenta de que el producto debe ser 15 al cubo, es decir, 3375. Las otras variables tienen un grado de libertad, es decir, hay una que podemos elegir con total libertad, lo que pasa es que no hemos usado las otras dos condiciones que lleva implícitas el problema: que el resultado está compuesto por números enteros (con lo cual, todos son divisores de 3375), y además, todos son distintos.

Tanteando un poco una vez que hayamos puesto todas las variables en función de una de ellas, en los centros de los lados sólo puede ir un cuadrado perfecto (1, 9, 25 o 225) y condiciona todos los demás valores, es decir, que la solución es única salvo giros y simetrías del cuadrado.

En la fila superior, por ejemplo, podría ir 3, 25 y 45, en la segunda 225, 15 y 1, y en la tercera, 5, 9 y 75. Como ya he dicho, sólo valen simetrías de estos valores.

jueves, 14 de abril de 2011

Un rectángulo cortado (II)

Enunciado

La clave es entender que los cortes han de ser paralelos a los lados del rectángulo inicial, ya que si no, el primer corte que no fuese paralelo daría lugar a una pieza que no podría tener todos sus lados paralelos.

Cortando las piezas cortadas

Cortando las piezas cortadas

Una vez entendido esto, la siguiente idea es que sólo ha podido dar tres cortes, o bien tres horizontales y tres verticales, o bien dos horizontales y uno vertical, o bien dos verticales y uno horizontal. En el caso de mezclar direcciones distintas, los cortes pueden no ser de lado a lado, si no sólo hasta separar la pieza del original.

Para hacer la última parte hay muchos procedimientos válidos, que se pueden ejemplificar con los casos que se han citado antes, aunque sea muy trabajoso. Sin embargo, hay un método muy elegante, que cuento a continuación.

Surge de probar en los casos más sencillos. Piensa lo que harías si los tres cortes fueran horizontales. Buscarías partir las piezas para que una parte fuese el cuadrado 7 por 7, y el otro el rectángulo 5x7.

Pues bien, la idea es partir cada trozo con un corte vertical de forma que forme un fragmento de 7/12 y otro de 5/12 (ambos referidos al total de la pieza en cuestión). Puesto que todas las piezas han quedado reducidas de la misma forma, se pueden volver a situar para formar la pieza deseada. En el dibujo se ejemplifica la forma.

domingo, 10 de abril de 2011

Un rectángulo cortado (I)

Enunciado

Este es un problema para estudiar tranquilamente, y con paciencia. Es imposible que uno de los cortes no sea paralelo a los lados, ya que sólo podemos dar dos cortes, y los lados de un rectángulo han de ser paralelos.

Tipos de cortes sobre un rectángulo

Tipos de cortes sobre un rectángulo

Hay tres tipos de formas de cortar, pero según por dónde cortemos puede haber muchas variantes. Los dos cortes horizontales sólo tienen dos variantes (el rectángulo gordo en el centro, o en un lado).

Si damos un corte horizontal y un vertical, tenemos dos grandes familias: el corte horizontal primero, que puede ser de tres tamaños, y los verticales, que pueden ser de cuatro formas posibles. También podemos dar el primer corte en vertical y saldrán dos variantes para el corte horizontal.

Por último, si damos los dos cortes verticales, hay hasta 16 formas diferentes de dividirlos. En el dibujo tenemos algunas de las formas de cortarlo.

Ahora, la segunda parte. En realidad, tratamos de conseguir siempre el mismo cuadrado 4x4, y el rectángulo que sobra, 5x4, y tratamos de que las piezas se parezcan, en cierta manera, a las que hemos cortado.

Si hemos cortado en horizontal, basta cortar tiras de 4 de largo, y unirlas.

Si hemos cortado en vertical, basta quitar una tira de 2 de la mayor, y de uno de las demás (nota: aquí cometimos un error, ya que si la tira es de 1 de ancho, no queda dividida en dos partes, habría que dividirla en un cuadradito de 1 y un rectángulo de 2x1, y añadirle la pieza complementaria de la segunda tira mayor)

Si hay una de cada clase, podemos usar las horizontales para la parte inferior del cuadrado y el rectángulo, y un fragmento de las verticales para las dos partes. Tenemos que tener en cuenta de nuevo la posibilidad de que tengamos una única tira vertical, de forma que haya que dividirla, y en ese caso cortar un fragmento "raro" en las verticales para que encajen, pero es posible.

sábado, 9 de abril de 2011

Una hormiga amenazada

Enunciado

Cuando hay que recorrer un laberinto, y la probabilidad de ir desde una cámara a otras se mantiene a lo largo del tiempo, hay una forma muy simple de calcular la probabilidad de acabar en una u otra salida, que se puede usar en cualquier tipo de laberinto.

Para empezar, las salidas se consideran las únicas posiciones estables (en este caso, la única salida es la muerte de la hormiga), y por pequeña que sea la probabilidad de llegar a ellas, la probabilidad de seguir en el laberinto queda multiplicada en cada unidad de tiempo por un factor, de forma que la probabilidad de no seguir en el laberinto y alcanzar una de las salidas crece de forma exponencial, es decir, que la probabilidad de no alcanzar nunca ninguna salida es 0.

En nuestro caso, la probabilidad de alcanzar alguno de los vértices "envenenados", por tanto, es 1.

El método para calcular la probabilidad de acabar en alguna de las soluciones, se plantea de la siguiente forma. Se usan tantas variables como nodos hay en el laberinto multiplicado por las salidas (si hay 6 nodos y 2 salidas, se usan 12 variables). Cada una de esas variables representa la probabilidad de acabar en una de las salidas partiendo de uno de los nodos. Después, para cada uno de los valores, se calcula dónde va a estar en el siguiente paso y con qué probabilidad. La probabilidad de llegar a la salida indicada desde ese inicio será igual a la suma de las probabilidades de llegar a la salida indicada desde el siguiente lugar, multiplicada por la probabilidad de llegar a él. El resultado, es un sistema de tantas incógnitas como hayamos usado y tantas ecuaciones como incógnitas. Seguro que será determinado, debido a un resultado de probabilidad.

En nuestro caso se pueden usar menos variables, ya que sólo hay dos tipos de casilla (según su posición respecto a los vértices envenenados). Unos, son los unidos con los envenenados (3, 4, 5 y 6) y otros, los que no (1, 2).

La probabilidad de llegar a 7 empezando desde 1, por ejemplo, la vamos a representar por x. La de llegar a 8 empezando desde 1, será 1 - x (ya que sólo hay dos salidas). Por simetría, la de llegar a 8 desde 2 será x y a 7 desde 2 será 1 - x.

La probabilidad de llegar a 7 desde 3 o 6, o de llegar a 8 desde 4 o 5 será y. La probabilidad de llegar a 8 desde 3 o 6, o de llegar a 7 desde 4 o 5 será 1 - y.

Si nos situamos en el punto 1, con probabilidad 1/3 la hormiga pasa a 2, 5 o 4, de donde tenemos la igualdad x = (1 - x)/3 + (1 - y)/3 + (1 - y)/3. Quitando denominadores y simplificando, 4x + 2y = 3.

Por otra parte, si nos situamos en un 5, por ejemplo, tenemos que pasa con probabilidad 1/3 a 8, 6 o 1, por lo que y = 1/3 + (1-y)/3 + (1-x)/3. De nuevo, quitando denominadores, 4y + x = 3. Tenemos dos ecuaciones, despejamos 2y en la primera, teniendo 2y = 3 - 4x, de donde 6 - 8x + x = 3, es decir que 7x = 3, por lo que x = 3/7.

Por tanto la respuesta a la segunda pregunta es que, partiendo del vértice 1, la probabilidad de morir en el 7 es 3/7 y la de morir en el 8 es 4/7.

También es posible simular mediante una sencilla hoja de cálculo el laberinto en cuestión y obtener un resultado de forma empírica.

jueves, 7 de abril de 2011

Triangulando números

Enunciado

Me ha gustado mucho la solución del comentario de Alex.

La idea es que, en efecto, si sumamos todos los números de los lados, para obtener la suma de cada lado, y luego sumamos los lados entre sí, habremos sumado tres veces los números de los vértices.

Entonces, como sabemos que la suma de los nueve números es 45, y los tres números más pequeños son 1, 2 y 3, la suma menor que podemos lograr es (45 + 6)/3 = 17, que en efecto se puede alcanzar con poco esfuerzo, poniendo el 5 y el 7 entre el 2 y el 3, el 4 y el 9 entre el 1 y el 3, y el 6 y el 8 entre el 1 y el 2.

Lograr una suma de 20 tampoco es complicado, hay que sumar entre tres números 15, por ejemplo 4, 5 y 6. Así, si sumamos 45 (la suma de todos) y 15 (la suma de los tres números), obtenemos 60, que sería la suma de los tres lados. Bueno, eso suponiendo que podemos situar los números restantes, que también es sencillo, colocando 1 y 6 entre 7 y 9, 2 y 4 entre 8 y 9, y 3 y 5 entre 7 y 8. Probablemente hay más soluciones.

Encontrar la suma mayor consiste en buscar tres números que sumen lo máximo posible, que deben ser 7, 8 y 9. Entonces 45 + 7 + 8 + 9 = 69, que es 23*3. Para ver si funciona, sólo hemos de tantear un poco, y lo conseguimos situando 1 y 6 entre 7 y 9, 2 y 4 entre 8 y 9 y 3 y 5 entre 7 y 8. No conseguiremos sumar más.

domingo, 3 de abril de 2011

19 puntos en un hexágono

Enunciado

Dividir un hexágono en 18 partes

Dividir un hexágono en 18 partes

La idea de manejar una cantidad tan grande de puntos sugiere trabajar con el principio de Dirichlet.

Se trata de encontrar 18 regiones que dividan el hexágono de forma que las distancias máximas en su interior sean menores que la distancia dada.

Como disponemos de 19 puntos, al menos dos puntos estarán en la misma región, de donde obtenemos la conclusión de que hay dos que están a menor distancia que la dada.

Las regiones no tienen porqué ser iguales, podríamos utilizar un compás empezando desde un vértice, con esa medida, y ir trazando circunferencias sobre circunferencias, para dejar el hexágono dividido.

Sin embargo, la división propuesta en el dibujo (dividir el hexágono en seis triángulos, y cada uno de ellos en tres partes uniendo el centro del triángulo con los centros de las caras) es muy elegante y simétrica. Los 18 cuadriláteros que formamos así tienen una diagonal mayor (máxima distancia) que se puede calcular fácilmente, ya que supone los 2/3 de la altura de un triángulo de lado 1, que es √3/2, por lo que coincide con la longitud propuesta, √3/3. Esta partición en 18 cuadriláteros, por tanto, soluciona el problema.

viernes, 1 de abril de 2011

Un problema de ciudades y carreteras

Enunciado

Grafo coloreado

Grafo coloreado

Este tipo de problemas se puede solucionar por "fuerza bruta", tomando un punto cualquiera de partida (si pasas realmente por todos y vuelves al inicial, da igual por cuál empieces) y procurando seguir todos los posibles caminos, hasta descartar que exista, lo que llevaría un cierto tiempo, ya que habría que descartar todas las posibilidades, o bien encontrar uno, que en esta ocasión no existe.

El truco que usaron los que propusieron el problema consiste en colorear el grafo de una forma similar a la de la imagen. Se colorean de colores diferentes aquellos nodos que tienen una carretera que los conecte. Si es posible hacerlo, se le llama grafo bipartito. Bueno, pues está claro de que si es un grafo bipartito, recorrer todos los nodos sin repetir usa la misma cantidad de nodos de los dos colores, ya que pasas de uno a otro cada camino. Pues bien, eso no es posible en nuestro grafo porque hay diferente cantidad de nodos de cada color.