domingo, 31 de agosto de 2008

Los 17 números

Enunciado

Lo primero que hago en problemas de este tipo es reducir la cantidad de elementos que aparecen en el problema. Pensemos que sólo tenemos un único factor primo. ¿Qué cantidad de números con este único factor primo deberíamos tener para poder garantizar que hay dos cuyo producto es un cuadrado perfecto?

Para empezar, hay que fijarse en cómo podemos saber que un número es un cuadrado perfecto, viendo su descomposición en números primos. Si hablamos de números que sólo tienen un único factor primo, serían de la forma 1, p, p2, p3, p4... Es fácil ver que la clave para que uno de estos números sea un cuadrado perfecto es que su exponente en p sea par (1, p2, p4, etc. Como lo que buscamos es que el producto de dos de ellos sea necesariamente un cuadrado perfecto, bastará que dos de ellos tengan la misma paridad en el exponente, es decir, que haya tres. Dos de ellos tendrán la misma paridad, y al multiplicarse obtendremos una potencia de p de orden par, que será un cuadrado perfecto.

¿Podemos hacer algo parecido cuando tenemos dos factores primos? Pongamos que todos los números sólo tienen a 2 y a 3 de factores primos. Un número formado por un producto de potencias de 2 y de 3 será un cuadrado perfecto cuando ambos primos estén elevados a potencia par (por ejemplo, 2436 = (2233)2). Si unimos un número suficiente de números de este tipo (5, concretamente), garantizaremos que dos de ellos tengan la misma paridad en ambos exponentes, y al multiplicarlos obtendremos un número con el exponente par en el primo 2 y en el primo 3, que será, según hemos explicado, un cuadrado perfecto.

Vistas estas observaciones, pasemos al problema tal y como se nos plantea. Los 17 números que consideramos no tienen un factor primo mayor que 7, es decir, se pueden descomponer en un producto de potencias de los primos 2, 3, 5 y 7.

Observemos la potencia a la que está elevado en ellos el primo 2. Puesto que son 17, habrá al menos 9 en los que esa potencia será par, o 9 en la que sea impar (por el principio de Dirichlet o del palomar, ya que en caso contrario sólo tendríamos 16 números). Tomemos estos nueve números. El producto de cualquier par de ellos tendrá un exponente par en el primo 2.

Observemos ahora la potencia del primo 3 en estos nueve números. Repitiendo la deducción, habrá al menos 5 que tendrán la misma paridad (par o impar) en la potencia. El producto de cualquier par de estos cinco números tendrá una potencia par en el primo 2 y también en el primo 3.

Si repetimos el proceso para el primo 5, habrá al menos 3 números que tengan la misma paridad en las potencias de 2, 3 y 5. Y, de nuevo, con la paridad en el factor 7, podemos garantizar que dos de estos números tienen la misma paridad en las potencias de sus cuatro factores primos, 2, 3, 5 y 7.

El producto de estos dos números será un cuadrado perfecto, pues tendrá los exponentes de sus cuatro factores primos pares, es decir, será de la forma 22a32b52c72d = (2a3b5c7d)2, que evidentemente es un cuadrado perfecto.

jueves, 28 de agosto de 2008

Vecinos perfectos

Enunciado

Como dicen los comentarios del enunciado, hay que crear un pequeño método a medida para resolver este problema en un tiempo razonable. Básicamente, la idea es estudiar qué vecinos puede tener cada número, y, a partir de ahí, ver si hay una única solución, o hay varias.

NúmeroPosibles vecinos
13, 8, 15
27, 14
31, 6, 13
45, 12
54, 11
63, 10
72, 9
81
97, 16
106, 15
115, 14
124, 13
133, 12
142, 11
151, 10
169

Posibles vecinos

Creamos una tabla con los candidatos a vecino de cada número, cosa que es bastante sencilla. La tabla es similar a la que vemos en el lateral. Se observa que sólo dos números, el 8 y el 16, tienen un único posible vecino, con lo que si es posible situarlos de la forma que se nos pide, estos dos números ocuparán los extremos.

Supongamos que empezamos por el 8, en uno de los extremos. Junto a él iría el 1. Sin embargo, hay cierta ambigüedad en el número que va a continuación. Pasemos al otro extremo, y situemos el 16. Junto a él, el 9. Como el 9 sólo puede ser vecino del 7 y el 16, al otro lado del 9 hay un 7. Por la misma razón, junto al 7 hay un 2, después un 14, después un 11, después un 5, después un 4, después un 12, después un 13, después un 3.

Al lado del 3 no puede ir el 1, ya que eso obligaría a situar después el 8 y no pondríamos los que aún nos faltan, de forma que tiene que ir un 6. Después, un 10, después un 15 y, por fin, el 1 y el 8, pues no quedan más números. De esta forma, el orden correcto en el que podemos situar los números sería: 16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8, o bien al revés.

domingo, 24 de agosto de 2008

¡Menudo numerito!

Enunciado

En primer lugar, hemos de comprobar qué dos números pueden ser tales que sus cuadrados sumen 53. Como la mitad de 53 es 26, el más grande debe ser mayor que 5. Debe ser 6 ó 7, pero no puede ser 8 o mayor, pues su cuadrado (64) es mayor que 53. Como 53 - 36 = 17, que no es cuadrado, no puede ser 6, y además 53 - 49 = 4, que es el cuadrado de 2. Así que la segunda y la última cifra deben ser 7 y 2.

De forma similar, llegamos a la conclusión de que 45 sólo puede ser suma de 9 y 36, por lo que los otros dos números son 6 y 3.

Así pues, tenemos cuatro posibilidades, 3267, 3762, 6237 y 6732. Para saber si hay uno o más de uno que cumple la última condición, habrá que comprobar si el número calculado a partir de restarle al número otro formado reordenando sus cifras es múltiplo de 99 y está entre 1000 y 2000. Aprovecho para dar un método sencillo para esto, ya que 99 = 9*11, ambos primos entre sí, de forma que podemos saber si un número es múltiplo de 99 mediante el criterio del 9 y del 11, es decir, sumando sus cifras para ver si es múltiplo de 9, y sumando cifras pares e impares por separado, y restando, para ver si lo es de 11.

En realidad, restar a un número otro obtenido por ordenación de cifras siempre da un múltiplo de 9 (¿podrías descubrir por qué?), de forma que el criterio clave será el del 11.

El primero, 3267, origina el -4356, que no está entre 1000 y 2000. De la misma forma, 6237 también es negativo, -1089. El número 3762 da 1089, que cumple las dos condiciones, ya que 1 + 0 + 8 + 9 = 18, y 1 + 8 = 9, y por otra parte, 1 + 8 - (0 + 9) = 0, que es múltiplo de 11. Sin embargo, 6732 origina el 4356, que tampoco está entre 1000 y 2000.

Por tanto el número buscado es, como han descubierto varios visitantes, el 3762.

jueves, 21 de agosto de 2008

Policubos

Enunciado

Este es un problema bastante difícil, ya que incluye una parte de la formación matemática poco frecuente, que se llama visualización espacial.

3-Policubos numerados

3-Policubos numerados

En primer lugar, es conveniente formar los policubos de orden cuatro a partir de los de orden 3, ya que son conocidos y es más fácil añadir un cubo que pegar 4 entre sí. Como es sencillo manipular los de orden 3, he puesto números distintos a los cuadrados "distintos" donde podemos añadir un nuevo cubo. Si es posible girar el policubo de forma que un cuadrado coincida con otro, el número es el mismo. Evidentemente, si el policubo tuviese caras "por detrás" distintas, habría tenido que hacer otras vistas, pero en este caso no ha sido necesario, pues al darle la vuelta coinciden con ellos mismos vistos de frente (son planos). Como vemos, el policubo más sencillo da lugar a tres de orden mayor, mientras que el otro da lugar a 7. Sin embargo, hay dos, como veremos, que coinciden.

Todos los 4-policubos

Todos los 4-policubos

En este dibujo he puesto todos los policubos de orden cuatro que construimos de la forma que he indicado arriba. Los que llevan las letras A, B y C son creados a partir del policubo de orden 3 "recto", mientras que los que llevan las letras B, C, D, E, F, G y H son creados a partir del policubo de orden 3 "doblado". En total, son 8. Es particularmente difícil distinguir entre el E y el H, ya que uno es simétrico respecto al otro, pero no son iguales, si intentamos poner uno en la misma posición que el otro, uno de los cubos acaba apuntando hacia otro sentido (trata de imaginártelo).

Descomponer en dos policubos

Descomponer en dos policubos

La segunda pregunta es más sencilla, y daba una pista fundamental por si te habías quedado sin dibujar algún policubo de los anteriores. Para descomponer la pieza, yo me he imaginado que partía de un cierto cubo e iba coloreando tres más "mentalmente", unidos al primero (observa que uno de los cubos no es visible en el dibujo, pero tú sí lo debes marcar como coloreado o no). Después, me fijaba si los otros cuatro que "sobraban" formaban o no una única pieza. Con este método he encontrado las cuatro descomposiciones posibles, que vemos en el dibujo que acompaña a este texto. La descomposición más sencilla es B + G, pero mucha gente encuentra también G + E. Como sólo piden dos, con esto estaría resuelto. Sin embargo, hay dos descomposiciones más, la D + B, que también es relativamente sencilla, y una muy extraña, que poca gente ve rápidamente, la E + H, que une a los dos 4-policubos más extraños.

La tercera pregunta era realmente difícil, ya que si te has dejado algún policubo sin dibujar es una pregunta muy sencilla, pero deja de serlo cuando tienes todos. Vamos a explicarlo. La figura a recubrir tiene 6 caras, las grandes tienen 8 caras de cubo visibles (cuadrados), las medianas, 4, y las pequeñas 2. En total, 28 cuadrados. Nuestros policubos pueden tapar, según dónde se pongan, entre 2 y 4 cuadrados cada uno.

Vayamos uno a uno probándolos. El A puede tapar 4 cuadrados, tanto en la cara mayor como en la mediana. El B y el C, pueden tapar 4 cuadrados de la cara mayor o 3 en la cara mediana. El D y el G, pueden tapar 4 cuadrados en la cara mayor, pero sólo 2 en las demás.

Colocando dos policubos

Colocando dos policubos

El policubo F puede tapar 3 cuadrados de la cara mayor, pero sólo 2 si se emplea en otro sitio. Por último, los policubos E y H pueden tapar 3 policubos de la cara mayor, pero también 3 si se les sitúa como se ve en el dibujo, tapando un cuadrado de la cara mayor y dos de otra cara.

Si sumamos todo estos números, en teoría podríamos cubrir 4 + 4 + 4 + 4 + 3 + 3 + 4 + 3 = 29, así que en principio parece que sí podríamos taparlo (por esto digo que si hemos olvidado alguno, la respuesta inmediata es que no, ya que obtenemos menos de 28 cuadrados tapados). Sin embargo, si tratamos de hacerlo veremos que fracasamos una vez tras otra ¿por qué?

Si revisamos la lista de cuadrados que podemos tapar, observamos que casi todos necesitan tapar cuadrados de la cara grande, así que a lo mejor por eso no hay suficientes. Podemos "perder" un cuadradito de todos los que podemos tapar, ya que el máximo que podemos tapar es 29 y tenemos que tapar 28, pero no más.

Vamos a fijarnos en cuántos de los 4-policubos necesitan ponerse en las caras grandes. El A no, puede ir en la lateral sin perder ningún cuadrado. El B y el C necesitan tapar 4 cuadrados de la cara grande para aprovecharse bien (aunque uno de los dos podría no estar del todo aprovechado). El D y el G, necesitan ir en la grande, tapando 4 cada uno. El F tiene que tapar 3 de la cara grande, y el E y el H necesitan tapar, para usarse bien, por lo menos uno de los cuadrados de la cara grande. En total, 21 cuadrados de las caras grandes, pero sólo hay 16 (8 + 8), de forma que no todos podrán ir ahí. aunque quitemos uno de los que cubre 4, y lo usemos tapando 3 en otra cara, seguiremos teniendo que tapar 21 - 4 = 17 cuadrados de las caras grandes, y sabemos que no se puede, pues sólo hay 16.

Por lo tanto, es imposible, aunque cuesta comprobarlo (desde luego, no se pueden probar todas las combinaciones posibles en un tiempo razonable). Probablemente, baste usar un único 4-policubo más para taparlo.

domingo, 17 de agosto de 2008

Un cuadrilátero especial

Enunciado

En mi opinión, sobra el adjetivo de convexo, ya que si no lo fuese, una de sus dos diagonales sería externa al cuadrilátero y no podría bisecar el área.

Estudiemos las relaciones que se plantean en un cuadrilátero en el que una diagonal biseca el área.

Primera diagonal

Primera diagonal

Una diagonal AC, como la que se ve en la figura, divide un cuadrilátero ABCD cualquiera en dos triángulos, ABC y ACD. Si ambos tienen la misma área, como propone el problema, tienen mucho en común, pues comparten un lado y el área.

Pensando en que cada uno de los triángulos cumplen la igualdad del área, es decir, su área es la mitad de la base por la altura, si tomamos como bases los lados comunes, llegamos a la conclusión de que tienen igual su altura sobre el lado común (AC en el dibujo).

Segunda diagonal

Segunda diagonal

Pensemos ahora en la otra diagonal, BD. Puesto que corta a la primera diagonal en un punto P, divide a cada triángulo de los que hemos visto en dos. Si observamos los dos triángulos que quedan a uno de los dos lados de la diagonal BD (por ejemplo, BCP y CDP), veremos que tienen un lado en común, CP, y la altura sobre ese lado igual (es igual a la de los triángulos originales, antes de trazar BD). Es decir, que tienen la misma área.

Ahora bien, si la segunda diagonal también biseca el área, los dos pares de triángulos de un lado tendrán la misma área que los dos del otro lado, y, puesto que son iguales en área entre sí, los cuatro triángulos en los que dividen las dos diagonales al cuadrilátero tienen la misma área.

Además, tienen todos ellos la misma altura sobre el segmento AC, como ya hemos visto, por lo que las bases que están apoyadas sobre este segmento, AP y CP son también iguales. Es decir, que P es exactamente el centro de AC.

Razonando de la misma forma con la otra diagonal, P también es el centro de BD, por lo que los triángulos opuestos (por ejemplo, APB y CPD) son iguales y por lo tanto los lados opuestos del cuadrilátero son paralelos, razonando por semejanza de triángulos (Teorema de Thales, por ejemplo).

jueves, 14 de agosto de 2008

La última nota

Enunciado

La idea para resolver este problema es, como dice el comentario primero del enunciado, probar criterios de divisibilidad para los números. Ya sabemos que al final obtiene una media que es un número entero, (71 + 76 + 80 + 82 + 91)/5, es decir, 80. Sin embargo, antes de añadir la última nota, la suma de las cuatro que había era divisible entre 4, pues la media daba entera también. Como la suma total es 400, si le quitamos la última nota y da un número divisible entre 4 es porque esa última nota es divisible entre 4, luego sólo puede tratarse de 76 o de 80. ¿Cuál de los dos será?

Supongamos que se trata de 76. Las cuatro primeras notas sumarán un total de 324, que es divisible entre 4 (da 81). Sin embargo, antes de incorporar la cuarta nota debe haber sido divisible entre 3. Este número es divisible entre 3, por lo que de nuevo necesitamos que la cuarta nota haya sido una divisible entre 3, pero ninguna de ellas lo es (ni 71, ni 80, ni 82, ni 91). Por lo que sabemos, es imposible que 76 haya sido la cuarta nota.

¿Podría haber sido 80 la cuarta nota? En ese caso, la suma de las cuatro sería 320, y podemos ver que al restarle 71 se obtiene el 249, que es múltiplo de 3. Es fácil ver que al restarle el 91 da un múltiplo de 2, y la primera y la segunda notas podrían haber sido cualquiera de las dos restantes.

El caso es que la última nota en introducirse fue el 80.

domingo, 10 de agosto de 2008

Transporte aéreo

Enunciado

Contando el tiempo a partir de la coincidencia de las 2 a.m., los vuelos desde Barcelona salen los múltiplos de 26 minutos, los de Alicante, los de 18, y los de Valencia, los múltiplos de 24. Evidentemente, la primera vez que coincidirán será en el primer múltiplo común, es decir, en su mínimo común múltiplo.

Como 26 = 2*13, 18 = 2*32 y 24 = 23*3, el mínimo múltiplo común será 23*32*13 = 936. En horas, esto es 15 horas y 36 minutos (dividiendo entre 60, y observando tanto el cociente como el resto).

Como hemos dicho antes, empezamos a contar a las 2 a.m., con lo que la coincidencia se produce a las 17 horas y 36 minutos, es decir, a las 5 y 36 de la tarde. El cierre de los aeropuertos se produce una hora después, a las 18 horas y 36 minutos.

Para saber la cantidad de vuelos que salen de Barcelona, sabiendo que han pasado 936 + 60 = 966 minutos, basta dividir esta cantidad entre 26, que da 37 (no exacto). Es fácil entender que en este caso han salido 37 vuelos a partir de las 2 a.m. del día indicado.

jueves, 7 de agosto de 2008

Circuito

Enunciado

Para hacer este problema podríamos plantearnos volver a dibujar el circuito con las flechas (y las operaciones) invertidas, ya que casi todas las preguntas nos obligan a seguir esa lógica. Sin embargo, con un poco de imaginación no es necesario.

En el apartado (a), si llega a la salida con 17, la última operación puede haber sido dividir por 2, y, en ese caso, habríamos llegado a esa casilla con 34, por lo que no podríamos haber llegado desde el centro (sumando 37), ni tampoco multiplicando por 6.

Es decir, que llegamos desde otro lado a la salida, sumando 8, por lo que hemos llegado a esa casilla con un 9, y sólo podemos llegar desde la casilla de multiplicar por 3, a la que habremos llegado con 3, desde la que a un número se le suma su siguiente.

La única manera de llegar a 3 sumando a un número su siguiente es partiendo de 1, de forma que ha salido con 1, le ha sumado 2 hasta la casilla de multiplicar por 3, ha pasado a la casilla sumar 8 y ha llegado con 17.

Para el apartado (b), basta hacer algo similar para el 83, que es el número con el que llegó Olga. Además, como sabemos que no pasa por la casilla central, lo tenemos más fácil.

De la misma forma que antes, no puede llegar al final desde la casilla dividir por 2, por idéntico motivo. Viniendo desde el otro lado podemos rápidamente deducir que ambas han partido con el número 12, y Olga ha pasado, sucesivamente, a 25, 75 y 83.

Claro, si Nuria siguió un camino distinto, tuvo que ir por el otro lado, y partiendo con un 12, obtendría 36, 246 y 123, con el que saldría.

Para el apartado (c), podemos entender que se puede llegar a esa casilla desde dos caminos. En un caso, el número llega multiplicado por 6, de forma que es par siempre, y del otro, necesariamente llega después de sumarle a un número su siguiente (con lo que obtenemos un número impar), y sumarle después 37, que es impar (con lo que obtenemos un número par), de forma que siempre es divisible por 2.

Para el apartado (d), tenemos que repetir el proceso de (a) y (b) usando el número 396. Si viene de sumar 8, antes era 388, y no puede proceder de multiplicar por 3, luego viene de sumar 37 y era 351. Claro que ese número debe venir de sumar un número a su siguiente, luego tenía que ser el 175. Pero este es mayor de 50.

Luego viene de dividir por 2, así que antes era aún mayor, el 792. Es fácil ver que tampoco puede venir de sumar 37 (es demasiado grande). Luego viene de multiplicar por 6, por lo que antes era 132. Antes de sumarle 24, era el 108, pero es demasiado grande para venir desde la entrada, por lo que venía de sumar 37, así que era el 71, que proviene de sumar 35 a su siguiente.

En resumen, que salió con un 35 (menor que 50), le sumó su siguiente y obtuvo 71, le sumó 37 y obtuvo 108, le sumó 24, hasta 132, lo multiplicó por 6 y consiguió el 792, y por último lo dividió por 2, saliendo con el conocido 396.

El apartado (e) es, con mucho, el más difícil. Si vamos por el borde, debemos fijarnos especialmente en las últimas operaciones. Es evidente que dividir por 2 puede dar lo mismo que sumar 8, por lo que esto no da ninguna pista.

Así, tenemos que fijarnos en las dos últimas operaciones. Por un lado, multiplicamos por 6 y dividimos por 2, que es lo mismo que multiplicar por 3. Por el otro, multiplicamos por 3 y sumamos 8. Ahí está la diferencia clave: si vamos por un lado, obtenemos un número que es múltiplo de 3, y si vamos por el otro no (un múltiplo de 3 deja de serlo si le sumamos 8, que no lo es).

domingo, 3 de agosto de 2008

Sumando potencias

Enunciado

Es evidente que lo que pretende este problema es que descompongamos esta suma en un producto que sea expresable con números enteros. Tal vez, lo más interesante sea que las potencias de 2 se puedan expresar como si se tratase de una única variable, que podría ser 2m. Supongo que todo el mundo sabe que 25m = (2m)5, así que el número que hemos de descomponer se puede expresar como un polinomio x5 + x + 1, donde x = 2m.

Valor XPolinomioFactorización
2 = 21355*7
3 24713*19
4 = 2210293*343 = 21*49 = 7*149
5313131*101

Tabla de valores

Aquí es donde te puedes encontrar con un dilema. ¿Se podrá descomponer siempre el polinomio, o se trata de una propiedad exclusiva de las potencias de 2? En el caso de una competición como la olimpiada, en la que el tiempo cuenta, puede tratarse de una manera de hacerte perder el tiempo. Calculemos unos cuantos valores para distintas x, que puede que nos sean de utilidad. Puedes verlos en la tabla del lateral.

La idea es utilizar los valores calculados para encontrar polinomios útiles para hacer la división. Evidentemente, el polinomio x5 + x + 1 no es divisible por x + 1 ni por x - 1, es decir, no tiene divisores enteros de grado 1 (si los tuviese, ya sabes que el término independiente dividiría al término independiente de x5 + x + 1, es decir, a 1).

Si vamos a probar a dividirlo con polinomios de grado 2, podemos probar más rápidamente si probamos valores de los que tenemos en la tabla, ya que tiene que proporcionar uno de los factores. El polinomio x2 - 1 cumple para 2, pero falla para los demás. Los polinomios x2 + 1 y x2 + x - 1 no cumplen ni siquiera el 2. Sin embargo, x2 + x + 1 proporciona valores que sí aparecen en la tabla: para 2, el 7, para 3, el 13, para 4, el 21, y para 5, el 31. Demasiada casualidad.

Si realizamos la división entre polinomios, observaremos que x5 + x + 1 = (x2 + x + 1)(x3 - x2 + 1), de forma que esta es la factorización que buscamos.

Es decir, que 25m + 2m + 1 = (22m + 2m + 1)(23m - 22m + 1). Además, es sencillo comprobar que ambos factores son mayores que 1, ya que 23m es mayor para todo m positivo que 22m.

Observa que en problemas de este tipo no siempre es útil convertirlo en un polinomio, ya que hay veces que la factorización podría depender realmente de que los sumandos sean una potencia de 2.