lunes, 28 de abril de 2008

Otra potencia de 3

Enunciado

Ya he expuesto anteriormente en el blog, en las categorías de primer ciclo y segundo ciclo, cómo calcular cuál es la última cifra de 32008 y la de 372008. Es mejor que leas detenidamente cómo se realiza ese cálculo, porque te puede dar ideas muy convenientes para trabajar en el próximo.

Bueno, ahora se trata de averiguar si 32008 - 1 es un número divisible entre 8 o no. Probablemente, lo primero que se te ocurra sea calcular las últimas cifras (concretamente, las últimas 3) del número 32008, para aplicar el criterio de divisibilidad del 8 (si las últimas cifras son divisibles entre 8, seguro que el número lo es). Sí, es posible. Seguro que hay un patrón en las últimas tres cifras de las potencias de tres, pero es posible que sea largo, muy largo. Tal vez tenga más de treinta potencias de longitud, y eso significa hacer muchas cuentas. No, hay otro sistema.

Veamos. El número 32 - 1 = 8 es un número divisible entre 8. Sin embargo, 33 - 1 = 26, pese a ser par, no es divisible ni siquiera entre 4. De nuevo, 34 - 1 = 80 vuelve a ser divisible entre 8. Y el número 35 - 1 = 242 no es tampoco divisible entre 8. ¿ves el patrón? Vamos a ver si lo formalizamos, es decir, si podemos seguir tranquilamente la cadena hasta 2008, sin calcular todas las potencias.

Supongamos que tenemos un n parecido a 2 o a 4, es decir, de los que 3n - 1 es divisible entre 8. ¿Qué pasará con el siguiente? En ese caso, 3n es una unidad más grande que un múltiplo de 8, es decir, es de la forma k*8 + 1. Si lo multiplicamos por 3, obtenemos 3n + 1, es decir, la potencia siguiente. Esa potencia, será de la forma 3*k*8 + 3, es decir, será 3 unidades más grande que un múltiplo de 8 (observa los casos de 27 y de 243), por lo que al restarle 1 no es divisible entre 8, aunque sí lo es al restarle 3.

Ahora bien, ¿y si tenemos un valor n parecido a 3, o a 5, es decir, de los que habría que restarle 3 para que fuese divisible entre 8? Entonces, 3n = k*8 + 3 para algún valor de k, y la siguiente potencia, 3n + 1, que se obtiene al multiplicar la anterior por 3, sería de la forma 3*k*8 + 3*3 = 3*k*8 + 8 + 1 = (3*k + 1)*8 + 1, es decir, sería una unidad más grande que un múltiplo de 8.

Con este par de comprobaciones, tenemos confirmado el patrón: ciertas potencias de 3 (las pares), son una unidad más grande que un múltiplo de 8, y las otras (las impares) son tres unidades mayores que un múltiplo de 8. La que nos interesa, 32008 es par, por lo que al restarle uno sí que es un múltiplo de 8.

jueves, 24 de abril de 2008

Potencia de 37

Enunciado

Para resolver la primera parte, la última cifra de 32008, mira la solución al problema de primer ciclo. ¿Ya la has visto? Pues sigamos con la de segundo ciclo.

La potencia con la que hemos de trabajar es 372008. Evidentemente, empezaremos por potencias menores, y fijándonos exclusivamente en la última cifra. Ya sabemos que esa última cifra procede exclusivamente del producto de las últimas cifras, así que no nos molestaremos en calcular nada más.

La última cifra de 372 es 9, procedente de 7*7 = 49.

La de 373 es 3, de multiplicar 9 (la de 372) por 7, que da 63.

La última de 374 es 1, procedente de 3*7 = 21.

La de 37 5 es 7, pues eso da 1*7.

Evidentemente, después de eso, volvemos a empezar, de forma que tenemos un ciclo de cuatro cifras que siempre se repiten en el mismo orden: 7, 9, 3, 1. Casualmente las mismas cifras que aparecen en las potencias de 3, aunque en orden inverso.

Y, de nuevo, 372008 tiene la misma última cifra que 374, por ser 2008 múltiplo de 4, y esta cifra es 1. Exactamente igual que 32008.

domingo, 20 de abril de 2008

Potencia de 3

Enunciado

Evidentemente, no podemos calcular a mano 32008. Si no vamos a hacer trampas (hay calculadoras en Internet que pueden calcularlo), debemos empezar por calcular las primeras potencias, poniendo especial cuidado en la última cifra. La primera potencia interesante es 32 = 3*3 = 9. Después, 33 = 9*3 = 27. Observamos que la última cifra es un 7. La siguiente potencia, 34 = 27*3 = 81, acaba en 1, y ese 1 lo obtenemos de multiplicar 7*3, que da 21.

Supongo que te habrás dado cuenta que para obtener la última cifra, no necesitamos calcular las demás, es decir, que sólo necesitamos saber la última cifra de la potencia anterior. Así, para sacar la última cifra de 35, basta multiplicar 1 por 3, y sabemos que es 3. La última cifra de 36 será, entonces, 9, y la de 37, 7. Así que para 38 volveremos a tener 1 en la última cifra.

En resumidas cuentas, se produce un ciclo que se repite potencia tras potencia. Del 3 al 9, de éste al 7 y de 7 a 1, y vuelta a empezar. Cada cuatro potencias, volvemos a tener un ciclo. La potencia que nos interesa, 2008, es múltiplo de 4 (es año bisiesto, ya sabes). Y, como el ciclo es de 4 números, todas las potencias múltiplos de 4 acaban en lo mismo. Como 34, todas acaban en 1. También 32008 acaba en 1.

jueves, 17 de abril de 2008

Cuestión de relojes

Enunciado

Supongamos que son las ocho. El reloj de Josep va diez minutos retrasado, de forma que en realidad marca las ocho menos diez (19:50), además, Josep cree que adelanta cinco minutos, de forma que Josep cree que son las ocho menos cuarto (19:45), es decir, que falta aún 15 minutos para llegar a la cita.

A la misma hora, el reloj de Víctor, que va cinco minutos adelantado, marca las ocho y cinco (20:05), pero como él cree que va diez minutos retrasado, Víctor cree que son las ocho y cuarto (20:15), de forma que lleva un cuarto de hora esperando a Josep.

De forma que Víctor llegará quince minutos antes a la cita, y esperará a Josep durante media hora. Deberían haber cambiado los relojes.

domingo, 13 de abril de 2008

Planeta octaédrico

Enunciado

Este problema es más complicado (o, por lo menos, más largo) de lo que parece a simple vista. Si tratamos de crear una de esas rutas por las aristas, de forma que pasen por todas, estamos, de nuevo, haciendo un problema de recorrido, pero si buscamos todas las rutas, también tenemos que hacer algo de combinatoria.

Ver que se pueden trazar rutas de este tipo es sencillo. Puesto que la ruta debe ser un circuito (acaba donde empieza), es evidente que en los vértices deben unirse una cantidad par de aristas, ya que por cada camino entrante hay uno que sale. En la figura que nos ocupa sí se cumple esto, porque en cada vértice concurren cuatro aristas.

Octaedro con vértices

Octaedro con vértices

Podemos nombrarlas, para aclararnos, como A (ciudad alta), B (otro vértice del ecuador, unido con A por una arista), C (polo norte), D (el otro vértice del ecuador, al lado opuesto a B), E (polo sur) y F (las antípodas de A). Una ruta del tipo que buscamos podría ser ABCDACFEBFDEA. Podemos confirmar que es válido porque pasa por todos los vértices dos veces (tres por el A, porque sale y llega a él), y por tanto usa todas las aristas, bien sea para entrar o para salir. Aunque debemos cuidar que no se repita ningún par de vértices (por ejemplo, EB y BE en la misma ruta). En total, siempre van a contar con 13 letras, siendo la primera y la última una A.

Si queremos hacer una estimación, podemos partir de cuatro caminos que salen de A, y que cada vez que lleguemos a un vértice (por primera vez) contamos con 3 caminos posibles. Si llegamos por segunda vez, sólo quedará un camino, salvo que volvamos a A, en cuyo caso quedarán 2 caminos. A partir de ahí, no hay más bifurcaciones, por lo que tendríamos un total de 4*3*3*3*3*3*2 posibilidades, lo que asciende a 1944 caminos. Sin embargo, algunos de estos caminos desembocan por tercera vez (y se acaban) en A antes de tiempo, por lo que el número real será inferior, y no conozco una alternativa mejor que contar uno a uno los caminos (me gustaría que si alguien la tiene, me informase). Mi idea consiste en trazar poco a poco los caminos, resumiendo en la medida de lo posible.

Partiendo de A, hay cuatro caminos que ofrecen simetría completa, por lo que vamos a contar a partir de uno de ellos, y luego multiplicaremos por 4. Supongamos entonces que empezamos por AB. Hay dos opciones a partir de aquí que son simétricas, doblar a C y doblar a E. De estas dos, bastará considerar sólo una, y luego multiplicar por dos los caminos. La opción de seguir a F hay que considerarla a parte.

Este bloque, entonces, lo empezamos con ABC.

Si volvemos a A (ABCA), tenemos dos opciones: D y E. Si llegamos a D (ABCAD), tenemos tres opciones (C, E, F). En C pasamos a F (ABCADCF) y volvemos a tener tres opciones, B, D y E. Por B, llegamos a E (ABCADCFBE) y sólo tiene dos opciones válidas (recuerda que no podemos llegar a A demasiado pronto): ABCADCFBEDFEA y ABCADCFBEFDEA. Si hubiésemos tirado por D, también pasamos a E y tenemos otras dos: ABCADCFDEBFEA y ABCADCFDEFBEA. Si hubiésemos tirado por E, sólo hay dos opciones más: ABCADCFEBFDEA y ABCADCFEDFBEA. Desde ABCAD, podíamos haber pasado a E como segunda opción, y nos habríamos encontrado con las 4 rutas siguientes: ABCADEBFCDFEA, ABCADEBFDCFEA, ABCADEFCDFBEA y ABCADEFDCFBEA. Por último, desde ABCAD, pasando a F, tenemos 6 rutas más, ABCADFBEDCFEA, ABCADFBEFCDEA, ABCADFCDEBFEA, ABCADFCDEFBEA, ABCADFEBFCDEA y ABCADFEDCFBEA. Por tanto, son 16 para el comienzo ABCAD. Si consideramos ABCAE, podemos contar otras 16, ABCAEBFCDEFDA, ABCAEBFCDFEDA, ABCAEBFDCFEDA, ABCAEBFDEFCDA, ABCAEBFEDCFDA, ABCAEBFEDFCDA, ABCAEDCFBEFDA, ABCAEDCFEBFDA, ABCAEDFBEFCDA, ABCAEDFEBFCDA, ABCAEFBEDCFDA, ABCAEFBEDFCDA, ABCAEFCDEBFDA, ABCAEFCDFBEDA, ABCAEFDCFBEDA y ABCAEFDEBFCDA. De momento, hemos analizado al completo ABCA, con un total de 32 rutas.

Si pasamos a D (ABCD), tenemos tres opciones: A, E y F. Desde ABCDA hay 12 posibilidades: ABCDACFBEDFEA, ABCDACFBEFDEA, ABCDACFDEBFEA, ABCDACFDEFBEA, ABCDACFEBFDEA, ABCDACFEDFBEA, ABCDAEBFDEFCA, ABCDAEBFEDFCA, ABCDAEDFBEFCA, ABCDAEDFEBFCA, ABCDAEFBEDFCA y ABCDAEFDEBFCA. Desde ABCDE, hay 16 posibilidades: ABCDEACFBEFDA, ABCDEACFEBFDA, ABCDEADFBEFCA, ABCDEADFEBFCA, ABCDEBFCADFEA, ABCDEBFCAEFDA, ABCDEBFDACFEA, ABCDEBFDAEFCA, ABCDEBFEACFDA, ABCDEBFEADFCA, ABCDEFCADFBEA, ABCDEFCAEBFDA, ABCDEFDACFBEA, ABCDEFDAEBFCA, ABCDEFBEACFDA y ABCDEFBEADFCA. Desde ABCDF, hay otras 16 posibilidades: ABCDFBEACFEDA, ABCDFBEADEFCA, ABCDFBEDACFEA, ABCDFBEDAEFCA, ABCDFBEFCADEA, ABCDFBEFCAEDA, ABCDFCADEBFEA, ABCDFCADEFBEA, ABCDFCAEBFEDA, ABCDFCAEFBEDA, ABCDFEACFBEDA, ABCDFEADEBFCA, ABCDFEBFCADEA, ABCDFEBFCAEDA, ABCDFEDACFBEA y ABCDFEDAEBFCA. Por tanto, hemos analizado por completo ABCD, con un total de 44 posibilidades.

Por último en la opción ABC, si pasamos a F (ABCF), tenemos otras tres opciones, B, D y E. Desde ABCFB hay 16 posibilidades, ABCFBEACDEFDA, ABCFBEACDFEDA, ABCFBEADEFDCA, ABCFBEADFEDCA, ABCFBEDACDFEA, ABCFBEDAEFDCA, ABCFBEDCADFEA, ABCFBEDCAEFDA, ABCFBEDFEACDA, ABCFBEDFEADCA, ABCFBEFDACDEA, ABCFBEFDAEDCA, ABCFBEFDCADEA, ABCFBEFDCAEDA, ABCFBEFDEACDA y ABCFBEFDEADCA. Desde ABCFD, hay 12 posibilidades, ABCFDACDEBFEA, ABCFDACDEFBEA, ABCFDAEBFEDCA, ABCFDAEFBEDCA, ABCFDCADEBFEA, ABCFDCADEFBEA, ABCFDCAEBFEDA, ABCFDCAEFBEDA, ABCFDEBFEACDA, ABCFDEBFEADCA, ABCFDEFBEACDA y ABCFDEFBEADCA. Desde ABCFE, hay otras 16 posibilidades: ABCFEACDEBFDA, ABCFEACDFBEDA, ABCFEADEBFDCA, ABCFEADFBEDCA, ABCFEBFDACDEA, ABCFEBFDAEDCA, ABCFEBFDCADEA, ABCFEBFDCAEDA, ABCFEBFDEACDA, ABCFEBFDEADCA, ABCFEDACDFBEA, ABCFEDAEBFDCA, ABCFEDCADFBEA, ABCFEDCAEBFDA, ABCFEDFBEACDA y ABCFEDFBEADCA. Así, la opción ABCF también tiene 44 posibilidades.

En conclusión parcial, ABC tendría 44 + 44 + 32 = 120 posibilidades, más otras 120 simétricas si tomamos ABE, como hemos dicho antes. Queda analizar ABF. De nuevo nos planteamos tres posibilidades, C, D y E. En este caso, de nuevo por simetría, ABFC y ABFE tendrán exactamente el mismo tipo de ramificaciones.

Si pasamos a C (ABFC), tenemos tres posibilidades, desde ABFCA hay 12 posibilidades, desde ABFCB 16, y 16 más desde AFCD (no creo que sea conveniente detallarlas todas, pero si alguien siente curiosidad, que pregunte). En total, 44 rutas (y las mismas en ABFE).

Si pasamos a D (ABFD), tenemos otras tres posibilidades, A, C y E. De nuevo, 12, 16 y 16 caminos se abren ante nosotros. Otras 44 rutas.

Por tanto, ABF tiene un total de 44*3 = 132 rutas. Después de este cálculo, el número de rutas que empiezan por AB es 120 + 120 + 132 = 372. Como la figura es simétrica, comenzar por otra arista cualquiera daría el mismo resultado, luego hay exactamente 372*4 = 1488 rutas distintas que empiezan (y acaban) en A.

Las otras preguntas son mucho menos difíciles de contestar. Si una arista queda intransitable, dos vértices quedan con un número impar de aristas. Si queremos saber cuántas no podremos recorrer en un circuito, habrá que elegir un vértice intermedio, y quitar dos, una a cada vértice, y recuperaremos la paridad de aristas en los vértices. En total, habremos perdido tres aristas, la intransitable y dos más. Necesariamente estas tres aristas comparten dos vértices, luego forman un triángulo (una cara completa).

Si se pretende solucionar el problema pasando más veces por aristas, sería como añadir caminos, pero sucede algo similar, debemos añadir dos aristas más que alteren la paridad de dos vértices, ya que la que los une está intransitable. Por tanto, deberemos recorrer dos aristas dos veces cada una (forman un triángulo con la arista prohibida) como mínimo para restaurar la ruta.

jueves, 10 de abril de 2008

El puente encantado

Enunciado

Este problema también es un problema de recorrido, como el del Una ciudad con tres islas. En este caso hay cinco zonas conectadas por puentes, y si aplicamos el razonamiento basado en la paridad de los recorridos, si hubiese que pasar por todos los puentes, cada zona debería tener un número par de entradas y salidas si es zona de paso, y el principio y el fin, un número impar./p>

En este caso la cosa se complica, ya que pasamos por todos los puentes menos por uno, y además luego hay que investigar de cuántas formas se puede hacer.

Afortunadamente, sabemos desde dónde empezamos (el lado derecho del río) y dónde acabamos (la isla superior). En la isla hay una cantidad impar de puentes (3), así que ninguno de ellos será el encantado. Sin embargo, en el lado derecho del río hay un número par de puentes (4). Uno de ellos es el puente encantado. Si miramos con atención las demás zonas, las otras dos islas tienen un número adecuado de puentes (2 y 4), pero la orilla izquierda del río tiene tres puentes. Eso quiere decir (por ser zona de paso) que también hay que quitar uno. ¿Cuál? Claramente, el que cruza de una orilla a otra. Ése es el puente encantado. Al quitarlo, puede que podamos hacer los recorridos.

numerando puentes

numerando puentes

¿Cuántos recorridos? Vayamos por partes. Vamos a poner nombres a las zonas y a los puentes. D, I serán las orillas, y B C y A, las islas de bajo, central y superior. los puentes podemos numerarlos, por ejemplo, como marca el dibujo.

En primer lugar nos encontramos con tres opciones.

Supongamos que usamos el puente hacia la isla inferior en primer lugar (D1B), luego hay que cruzar a la isla central (D1B2C), y podemos hacer tres cosas: pasar a la otra orilla (D1B2C3I), volver a la primera (D1B2C4D), o pasar a la otra isla (D1B2C5A).

Siguiendo la primera de las posibilidades (D1B2C3I) no queda más remedio que pasar a la isla superior (D1B2C3I7A), y de aquí sólo tenemos dos rutas: pasar primero a la isla inferior, en cuyo caso sólo nos queda volver a la otra orilla y retornar a la isla (D1B2C3I7A5C4D6A), ruta 1, o bien cruzar a la isla, en cuyo caso tendremos que volver a la isla central y volver a la superior (D1B2C3I7A6D4C5A), ruta 2.

Siguiendo la segunda posibilidad (D1B2C4D), nos obligamos a pasar a la isla superior (D1B2C4D6A), y de nuevo se plantean dos cosas: pasar a la otra orilla, con lo que tendremos que pasar a la isla central y de ahí a la superior (D1B2C4D6A7I3C5A), ruta 3, o bien pasar a la isla central, de donde iremos a la orilla izquierda y a la isla superior (D1B2C4D6A5C3I7A), ruta 4.

Con la tercera posibilidad (D1B2C5A), pasamos directamente a tener dos opciones: pasamos a la orilla derecha, de donde vamos a la isla central, a la otra orilla y de nuevo a la isla superior (D1B2C5A6D4C3I7A), ruta 5, o bien pasamos a la orilla izquierda, de donde pasamos a la isla central, a la orilla derecha y a la isla superior (D1B2C5A7I3C4D6A), ruta 6.

Ya hemos agotado las posibilidades del primer puente, si pasamos por el puente 4 a la isla central (D4C), podemos hacer tres cosas (a partir de ahora, sólo resumiré las rutas): D4C2B1D6A, de donde obtenemos D4C2B1D6A5C3I7A, ruta 7, y D4C2B1D6A7I3C5A, ruta 8, D4C3I7A, de donde obtenemos D4C3I7A5C2B6A, ruta 9, y D4C3I7A6D1B2C5A, ruta 10, D4C5A, de donde tenemos D4C5A6D1B2C3I7A, ruta 11, y D4C5A7I3C2B1D6A, ruta 12.

Por último, nos queda el último puente válido, el 6, hasta la isla de arriba (D6A), que nos ofrece dos posibilidades: D6A5C, de donde sale D6A5C2B1D4C3I7A, ruta 13, la opción de cruzar a la orilla derecha no es posible, por no pasar por todos los puentes, y D6A5C4D1B3I7A, ruta 14, y D6A7I3C, de donde sale D6A7I3C2B1D4C5A, ruta 15, D6A7I3C4D1B2C5A, ruta 16, y una opción que tampoco vale, porque no pasa por todos los puentes, ya que vuelve a la isla superior por el puente 5.

esquema

esquema

En total, 16 rutas diferentes posibles, que son todas las indicadas arriba.

Es posible abordar este problema de una forma más cómoda si vamos construyendo todas esas rutas como un árbol, fijándonos en cada rama en los puentes que hemos cruzado, y en pasar al sitio correcto a través de cada puente.

domingo, 6 de abril de 2008

Una ciudad con tres islas

Enunciado

Este problema es un problema típico de recorrido, equivalente a recorrer un dibujo sin levantar el lápiz del papel, unir una serie de puntos, y otros pasatiempos.

Lo más difícil para muchos fue entender que un circuito quería decir que el punto de partida y el de llegada era el mismo, mientras que un recorrido significa partir de un lugar y llegar a otro. Con este plano de islas se puede hacer un recorrido, pero no un circuito.

Hay que observar que si nos fijamos en un trozo de tierra aislada (sea la costa, o una cualquiera de las islas), suponiendo que sólo podamos pasar por los puentes y que sólo podamos usar una vez cada puente, cuando el autobús del circuito entre en la zona, gastará un puente, y cuando salga, gastará otro. Eso quiere decir que cada vez que pase por una de las cuatro zonas, gasta dos de los puentes que tiene esa zona. Si un circuito se puede trazar, está clara que todas las zonas deberían tener una cantidad par de puentes que lleguen a ella.

En nuestro caso, las dos islas menores tienen sólo tres puentes que comuniquen con ellas. Por eso, si pasa por una de esas islas el autobús, usará un puente para entrar y otro para salir, con lo que sólo quedará un puente sin usar. Si vuelve a entrar el autobús, estará atrapado dentro de la isla.

¿Podríamos trazar un recorrido? Sí, si sale de una isla y acaba en la isla contraria, como es fácil comprobar. Pero no un circuito, por lo que antes se ha comentado.

Plano con solución

Plano con solución

¿Podríamos poner un puente más que solucionara el problema? Para hacer par a la vez los puentes de las dos islas, habría que añadir o quitar un puente entre ellas. Como no existe ninguno, sólo tenemos la posibilidad de añadirlo. Una vez añadido, hay que comprobar que efectivamente se puede hacer el circuito (ver en el dibujo).

jueves, 3 de abril de 2008

Sumafrutas

Enunciado

Al ver un tablero con números ocultos tras símbolos, la opción más fácil es buscar los que más se repitan. En este caso, las tres peras, sumadas, dan 15. Eso quiere decir que la pera vale 5.

Una vez que tenemos un valor, buscamos otra fila o columna con frutas repetidas, y vemos la manzana. Dos manzanas y una pera suman 7, por lo que cada manzana debe valer 1.

Ya no quedan filas ni columnas que nos den tanta información. Ahora, podemos empezar a trabajar con hipótesis. El limón (sí, es un limón), más la manzana más las cerezas suman 6, es decir, que limón más cerezas suman cinco. Eso quiere decir que las cerezas pueden valer 1, 2, 3 o 4. Sin embargo, cuando sumas las cerezas a la pera y a las fresas suma 17, es decir, que cerezas mas fresas suman 12. Fíjate que cada fruta sólo puede ser un número de una cifra, así que las cerezas no pueden valer 1 ni 2, ya que las fresas tendrían que valer más de 9. Así que las cerezas sólo pueden valer 3 o 4, y las fresas 9 o 8.

En resumen, si las cerezas valen 3, el limón vale 2, las fresas 9 y la pera 5 y la manzana 1. Esta solución es correcta.

Si las cerezas valen 4, el limón tiene que valer 1, como la manzana. En este caso, las fresas podrían valer 8. En este caso, también cuadra todo, pero el limón y la manzana vale lo mismo. En el enunciado no dice que frutas distintas tengan valores distintos, así que esta es otra solución, aunque normalmente se suele descartar por ser distintas las frutas.