domingo, 28 de septiembre de 2008

Un club y muchos comités

Enunciado

Evidentemente, tratar de tantear con tantos miembros es difícil. Yo traté de tantear con un club de 9 miembros y comités de 3. Si los miembros son A, B, C, D, E, F, G, H e I, el comité ABC hace que pueda existir el comité ADE, AFG y AHI, pero A no puede estar en ningún otro comité, ya que no puede repetirse otro miembro, y sólo puede haber cuatro parejas formadas con los distintos miembros del club.

De la misma forma, en un club de 25 miembros, cada miembro concreto podría estar simultáneamente en un máximo de 6 comités, ya que los 24 restantes sólo pueden formar 6 conjuntos disjuntos.

Imagina que les dan una carta (asignación) a cada miembro para decirle en qué comité está. Si cada uno de los 25 miembros ocupa plaza en 6 comités, habrá un total de 25*6 = 150 asignaciones de un miembro a un comité de 5 personas. Como 150/5 = 30, éste es el máximo número de comités que pueden existir.

También se puede razonar por combinatoria, como sugiere el segundo comentario.

jueves, 25 de septiembre de 2008

El fósil de un número

Enunciado

Puesto que buscamos un fósil impar, ninguna de las cifras del número que buscamos puede ser par.

Como todas sus cifras deben ser diferentes, para ser lo más grande posible deberíamos usar todas las cifras impares, es decir, el 1, el 3, el 5, el 7 y el 9. Sin embargo, el producto de todos estos números es el 3*5*7*9 = 945, y tiene una cifra par, de forma que al final tendría un fósil par.

Por tanto, tenemos que usar cuatro cifras. Quitar la más pequeña, el 1, no ayuda, pues el producto seguiría siendo el mismo, de forma que probamos a quitar el 3, así que el producto 5*7*9 = 315, y 3*5 = 15, proporciona un fósil impar, el 5.

Ya sabemos que debemos usar los números 1, 5, 7 y 9, y para que sea lo mayor posible pondremos los mayores en las posiciones más significativas (más a la izquierda). El número buscado es, entonces, el 9751.

lunes, 22 de septiembre de 2008

¡Manolo, que es tu cumple!

Enunciado

Puesto que se le deshacen 2/5 de los bombones, y luego tiene 1/8 más (es decir, 9/8), eso quiere decir que los 21 bombones que compra equivalen a 2/5 + 1/8 de la cantidad inicial (es decir, que repone los derretidos y añade 1/8 más).

Como 2/5 + 1/8 = 16/40 + 5/40 = 21/40, concluimos que 21 son los 21/40 del total, es decir, que el total inicial sería 21*40/21 = 40 (fíjate que para hallar los 21/40 de algo, se multiplica, y para sacar el total de la fracción, se hace la operación contraria, se divide por 21/40).

Dicho de otra forma, al principio llevaba 40 bombones, se le derritieron 2/5, es decir, 16 bombones, y compró 21, es decir, que se presentó con 45, que es 5 (1/8) más que al principio.

Como nos han dicho que su intención era dar dos bombones a cada uno de la clase, eso quiere decir que tiene 20 compañeros. Lo que no sabemos es si se contaba a él mismo o no.

viernes, 19 de septiembre de 2008

Círculos

Enunciado

Este problema es uno de los más interesantes que me he encontrado de este nivel. Por supuesto que se puede resolver por tanteo, pero tanteando se pueden descubrir varias cosas que lo simplifican, hasta agotar la totalidad de las soluciones.

Lo primero que se hace con estos problemas es estudiar en cuántas sumas aparece cada uno de los números que situamos en los círculos. Observa que todos intervienen en dos sumas, exactamente. Por eso, al sumar todos los resultados (18 + 14 + 11 + 14 + 16 + 17 = 90) da el doble que la suma de los dígitos (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45). Si diese otra cosa, sería imposible. Como en principio no parece haber más pistas, traté de tantear un poco (empezando por donde estaban las sumas más grandes), y descubrí un curioso fenómeno.

Supongamos que ponemos un 5, por ejemplo, entre el 18 y el 17. Los dígitos que están entre el 18 y el 14 deben sumar 13, para que al añadirlos a 5 den el 18, y por tanto el que hay entre el 14 y el 11 debe ser 1, para que 13 + 1 sea igual a 14. De la misma forma, el que está entre el 16 y el otro 14 debe ser 4, y la suma de los que hay entre el 17 y el 16 deben sumar 12, para que cuadren las sumas. De esta forma, podemos sacar los números que van en los vértices del triángulo central (en el ejemplo, 5, 4 y 1), y las sumas de los otros por parejas, lo que hace mucho más rápido su cálculo.

Primera solución

Primera solución

La regla que obtenemos es que, si ponemos un número entre el 17 y el 18, el del vértice superior debe valer 4 unidades menos, y el del otro vértice, una unidad menos. De forma que lo mínimo que puede ir en ese vértice es un 5 (como hemos visto, 1 en el de arriba y 4 en el otro). Las sumas de las otras parejas son, respectivamente, en el sentido de las agujas del reloj partiendo del 5, 13, 10 y 12. Como hay que usar el 2, sólo puede ser 2 + 8 = 10, el 3 irá en 3 + 9 = 12, y los restantes, 6 + 7 = 13. La figura queda como la primera de la imagen.

¿Será la única solución? Si probamos a poner un 6, los otros vértices del triángulo son 2 y 5, y las sumas, 12, 9 y 11. De nuevo, el 1 sólo puede ir en 1 + 8 = 9, y el 3 no lo podemos poner, pues 6 y 8 están usados ya.

Si ponemos un 7, los otros vértices son 3 y 6, y las sumas son 11, 8 y 10. El 9 lo podemos poner como 9 + 1 = 10, pero entonces el 2 no se puede usar (9 y 6 están usados). También podemos poner 9 en 9 + 2 = 11, y el 1 tampoco se puede usar, pues 9 y 7 están usados.

Segunda solución

Segunda solución

Si ponemos un 8, los vértices son 4 y 7, y las sumas 10, 7 y 9. El 9 sólo podría ir en 9 + 1 = 10, y 6 sólo en 6 + 3 = 9, y los otros dos serían 2 + 5 = 7, lo que daría otra solución.

Por último, si ponemos un 9, los vértices serán 5 y 6, y las sumas, 9, 6 y 8. El 8 tendría que usarse en 8 + 1 = 9, pero el 7 no podría usarse.

Luego sólo hay dos soluciones, salvo que cambiemos de sitio los sumandos que no están en un vértice, que son intercambiables.

lunes, 15 de septiembre de 2008

El menor perímetro

Enunciado

Si tratamos de dibujar varios triángulos que tengan la misma circunferencia inscrita, descubriremos que lo que tenemos que hacer es marcar tres puntos sobre la circunferencia y trazar las tangentes hasta que se corten. Es más, podemos fijar uno de los puntos y seguiremos obteniendo todos los triángulos posibles.

Un par de ejemplos

Un par de ejemplos

Como uno de los ángulos de la familia de triángulos que estamos estudiando es fijo, eso significa que dos de los puntos serán fijos, y además el tercer punto estará en el arco mayor comprendido entre ambos. En el dibujo he puesto dos de estos triángulos. A los vértices los he llamado A, B y C (A es el de ángulo fijo), y los puntos de tangencia, respectivamente opuestos a A, B y C, serán P, Q y R.

Es fácil ver que hay una parte del perímetro que está fija, la que va desde R hasta Q pasando por A, y el resto es la que puede variar. Además, como la distancia BP es la misma que BR, por simetría, y, de la misma forma, la distancia CP es la misma que CQ, en realidad sólo hay que tratar de que la distancia BC sea mínima (el perímetro total es la suma de RA, QA (fijas), RB, BP, QC, PC, y están repetidas dos veces).

Supongo que pronto habrás sospechado que el triángulo de menor perímetro es el isósceles, pero hemos de demostrarlo, y no es fácil.

Trazando lineas auxiliares

Trazando lineas auxiliares

Si trazamos las líneas entre el centro de la circunferencia (al que llamamos O, como es tradición) y los vértices B y C vemos aparecer unos triángulos rectángulos muy interesantes, BPO y CPO. La longitud PO es un radio de la circunferencia, que es también fijo, llamémosle r, y por tanto tenemos que PB = r*cotg(B/2) y PC = r*cotg(C/2). De forma que BC = r*(cotg(B/2) + cotg(C/2)). Como r es constante, sólo hay que encontrar los valores de B y C para los que cotg(B/2) + cotg(C/2) es mínimo.

Además, hay una relación importante entre B y C, ya que A + B + C suman 180 grados, y A es fijo, por lo que B + C es una constante también. Esto puede sernos útil más adelante.

Tratemos de factorizar ahora cotg(B/2) + cotg(C/2) = cos(B/2)/sen(B/2) + cos(C/2)/sen(C/2) = (cos(B/2)*sen(C/2) + sen(B/2)cos(C/2))/(sen(B/2)sen(C/2)) = sen((B + C)/2)/(sen(B/2)sen(C/2)). Es evidente que sen((B + C)/2) es constante, por serlo B + C, por lo que ahora hay que encontrar el valor para el que sen(B/2)sen(C/2) se hace máximo.

Probablemente conoces las fórmulas que transforman un producto en una suma, y es el momento de aplicarlas, de manera que sen(B/2)sen(C/2) = (cos((B - C)/2) - cos((B + C)/2)/2. Está claro que, de nuevo, el segundo sumando (cos((B + C)/2)) es constante por serlo B + C, de forma que habrá que conseguir que cos((B - C)/2) sea lo mayor posible.

El valor de el ángulo (B - C)/2 está comprendido entre -90 y 90 grados, y en ese intervalo el valor del coseno máximo se alcanza cuando (B - C)/2 = 0, momento en el que B = C, por lo que el triángulo que buscábamos es isósceles.

Es posible que exista una demostración sin usar trigonometría, pero no creo que sea sencilla.

jueves, 11 de septiembre de 2008

Capicúas

Enunciado

La táctica que debemos adoptar es clara: vamos a tratar de encontrar un atajo para sumar todos los capicúas que debería haber sumado Juan, y después le restaremos la cantidad que él ha obtenido. Así, determinaremos cuál ha dejado de sumar.

Como deberíamos escribir uno sobre otro todos los capicúas de cuatro cifras, lo primero que debemos plantearnos es un sistema mediante el cual nos aseguremos de tenerlos todos, y después contar cuantas cifras de cada clase hemos usado.

La primera y la última cifra (la de las unidades, y la de unidades de millar) deben ser iguales, y no pueden ser cero, pues se consideraría que el número tiene sólo tres cifras. Así que para la primera cifra tenemos nueve posibilidades. La segunda y la tercera, que también son iguales, sí pueden valer cualquier cifra, incluyendo el cero, de forma que tenemos diez posibilidades.

Si nos fijamos, entonces, al ponerlos en una columna (que será altísima), cada una de las nueve cifras de las unidades aparecerá repetida diez veces (porque, si fijamos una de ellas, sólo podremos escribir diez capicúas distintos), así que la suma de esa columna será (1 + 2 + ... + 9)*10 = 10*(1 + 9)*9/2 = 450. Sitúo un 0 en las unidades de la suma, y me llevo 45.

En la columna de las decenas, sin embargo, aparecerán diez cifras distintas, pero repetidas cada una de ellas nueve veces. La suma será 9*(0 + 1 + ... + 9) = 9*(9 + 0)*10/2 = 405. A esta cifra hay que sumar los 45 que nos llevamos, que nos proporciona un total de 450. De nuevo, situamos un cero y nos llevamos 45.

En la columna de las centenas, la suma será exactamente igual que la de las decenas, que para eso son capicúas, y dará de nuevo 405. Como nos llevábamos 45, vuelve a dar 450, de nuevo otro 0 y nos llevamos 45.

En la última columna, la de las unidades de millar, la suma es idéntica a la de las unidades, 450. Si le añadimos las 45 unidades de millar que nos sobraban de las centenas, tenemos 495, que son la cantidad definitiva de unidades de millar que tenemos.

En total, la suma debería de dar 495000. Como a Juan le daba 490776, vemos que la diferencia es exactamente 4224, que como no podía ser de otra forma, es capicúa. Y es el que le faltaba, claro.

lunes, 8 de septiembre de 2008

Rodeado de circunferencias

Enunciado

Tres círculos con radios

Tres círculos con radios

Como siempre en los problemas de geometría, hay que trazar algunas líneas que nos aportan mucha información. En este caso (como casi siempre) se trata de radios, que van desde los centros de las circunferencias, hasta los puntos de tangencia. Como los radios son perpendiculares a las tangentes, pertenecen cada dos de ellos a las dos semirrectas de la misma recta, es decir, que entre los 6 radios forman un triángulo, que además es equilátero, de lado 10 cm (el diámetro es 10, luego el radio es 5).

Además, si pintamos de diferentes colores las zonas que componen este triángulo, podemos apreciar que la parte que no está entre las tres circunferencias (la que está dentro de las circunferencias), forma tres arcos de circunferencia, cada uno de ellos de 60 grados, es decir, que es el arco del uno de los vértices de un triángulo. El área de los tres, si se sumara, sería 60 + 60 + 60 = 180, media circunferencia. Es decir que el área que buscamos es el área del triángulo menos el arco de media circunferencia de radio 5.

El área de un triángulo equilátero se calcula dividiéndolo en dos rectángulos mediante una altura, y aplicando el Teorema de Pitágoras. Así, la altura al cuadrado más medio lado al cuadrado es el lado completo al cuadrado, es decir, que la altura es la raíz cuadrada de la raíz de 3 multiplicada por la mitad del lado, en nuestro caso 5√3. El área, entonces, será 10*5√3/2 = 25√3.

El área de medio círculo será 25*π/2, de donde el área de la zona que se nos pide es 25√3 - 25*π/2 ≅ 4,0313.

jueves, 4 de septiembre de 2008

Alienígenas

Enunciado

Evidentemente, no podemos dividir la cantidad de ojos entre ninguna cantidad, ya que no todos tienen la misma cantidad de ojos, y no se puede hacer bien el reparto.

Observa, sin embargo, que sí que hay la misma cantidad de alienígenas de cada especie. Los podemos agrupar en una cantidad desconocida de grupos, de forma que en cada grupo haya un alienígena de cada especie, y no sobrará ninguno.

¿Sirve esto pra algo? Cuenta la cantidad de ojos de cada grupo. Habrá 4 ojos del de 4 ojos, 6 del de 6, 8 del de 8 y 12 del de 12. En total, en cada grupo habrá la misma cantidad de ojos ¡30 ojos para cuatro alienígenas!

Ahora sí podemos (intentar) dividir el total de ojos entre algo, entre 30, para saber cuántos grupos de este tipo hay. Digo intentar porque 5120 no es divisible entre 30, de forma que hay algo que no funciona. Lo más próximo posible sería 170, es decir, 170 extraterrestres de cada uno de los tipos, que serían 170*4 = 680 extraterrestres en total, pero esto haría un total de 170*30 = 5100 ojos, con lo que habría 20 ojos "de sobra". También podríamos decir que hay 171 extraterrestres de cada tipo, pero entonces faltarían 10 ojos en el recuento.

A partir de aquí, sólo cabe dar dos explicaciones: o el enunciado está mal (puede que no hayan dicho que hay una raza con un número distinto de ojos, o una de las razas tiene una cantidad distinta de ojos, o bien el recuento total de ojos está mal), o bien el enunciado es correcto, pero en realidad hay 171 extraterrestres de cada tipo, aunque a uno de ellos, de los de 12 ojos, le faltan 10 que perdió en un accidente (vamos, que es tuerto, el pobre).

martes, 2 de septiembre de 2008

El problema Internacional

Enunciado

Este es el problema internacional del mes. Tengamos en cuenta que se trata de un problema muy difícil. Vamos a poner muchos ejemplos de esta situación en una tabla, de forma que comprobemos que no se cumple en todos los casos, y tratar de buscar un patrón.

NúmeroCotaMayor primoS/N
385N
41017S
51313N
61537S
7175N
82013N
92241S
1024101S
112661S
122829S
133117N
1433197S
1535113S
1637257S
173929N
184213N
1944181S
2046401S
214817N
225097S
235253S
2454577S
2557313S
2659677S
276173S
2863157S
2965421S
306753N
316937N

Pruebas para el problema

Está conjeturado que hay infinitos primos de la forma n2 + 1, pero no está probado, de forma que es evidente que no se puede utilizar este resultado. Sin embargo, es evidente que si el número n cumple esta condición, el primo es más grande que la cifra pedida, siempre que n sea mayor que 2.

Hay un resultado que puede o no ser conocido, que es que todo primo que pertenece a la descomposición de n2 + 1 o es 2, o es de la forma 4k + 1. Además, todo primo de la forma 4k + 1 pertenece a la descomposición de n2 + 1 para algún n. Estos resultados, si bien dan lugar a distintas vías de solución del problema, no son imprescindibles para su solución, como veremos.

También es conocido, aunque no fácil de probar, que hay infinitos primos de la forma 4k + 1 (en general, hay infinida de primos en toda sucesión de la forma ak + b, para a y b primos entre sí). De nuevo, esto da lugar a interesantes vías de solución, aunque ninguna de ellas es imprescindible.

Ahora bien, si miramos con atención la tabla, hay algo que llama la atención. Aunque siguiéramos calculando para números mayores, no hay, aparentemente, una sucesión de valores para los que se cumpla, pero cuando no se cumple, siempre hay un valor anterior en el que ese primo salía y sí se cumplía, excepto para los primos 13 y 5. Esta circunstancia es muy difícil de apreciar con pocas muestras, de forma que tal vez sea conveniente disponer de una amplia selección.

Una vez que hemos dado con una intuición que nos permita trabajar, vamos a probar la existencia de infinitos números n como los que nos piden.

Vamos a dar un primer paso: supongamos que tomamos un p cualquiera, primo mayor que 20 (para que luego podamos aplicar una desigualdad con comodidad), y que divide a un cierto número k = m2 + 1 para un número natural m. Veamos que existe un valor n que cumple que n es menor que p/2 y p también es un divisor de n2 + 1.

Bueno, está claro que si m > p y p divide a m2 + 1, también divide a (m - p)2 + 1 = m2 + 1 + 2p + p2, de forma que podemos encontrar, bajando poco a poco, un valor m1 que cumpla las condiciones de que m1 < p y que p divide a m12 + 1.

Ahora bien, si m1 < p/2, tomamos n = m1, y en caso contrario, p/2 < m1 < p, tomamos n = p - m1. Está claro que 0 < n < p/2, y p divide a n2 + 1 = (p - m1)2 + 1 = p2 - 2p + m12 + 1. En cualquier caso, tenemos ese valor n.

Ahora, vamos con el segundo paso: para todo p, dado el n encontrado antes con esas dos condiciones, tenemos que p > 2n + √2n.

Llamemos ahora k al número p - 2n (nuestro objetivo es ver que es mayor que √2n). Tenemos que n = (p - k)/2 y que p divide a (p - k)2/4 + 1 = ((p - k)2 + 4)/4. Luego p divide al denominador, a (p - k)2 + 4 = p2 - 2p + k2 + 4. Por tanto, p divide a k2 + 4. Eso quiere decir que k2 + 4 es mayor que p, por lo que k es mayor que √(p - 4). Claro, que p - 4 = 2n + k - 4 > 2n + √(p - 4) - 4. Observamos que √(p - 4) es mayor que 4 siempre que p sea mayor que 20, de forma que (p - 4) > 2n, y resulta que p = 2n + k > 2n + √2n, como se quería ver.

Parece que ya estamos cerca, pero falta un paso más. ¿Hay infinitos n con esta condición? Veamos que así es.

Supongamos que no hay infinitos n que cumplan esta condición. Por ello, el conjunto de primos que dividen a los números de la forma n2 + 1 también es finito (ya que si fuese infinito, habría una cantidad infinita de p, y por tanto de n, que cumplen esta condición, ya que recordemos que p divide siempre a un n2 + 1 que cumple esta condición de cota). Ahora bien, tomemos m el producto finito de los primos p que dividen a los números de la forma n2 + 1. El número m2 + 1 es primo con m, ya que su número anterior es múltiplo de m, y por tanto sus factores primos no pertenecen al conjunto de todos los factores primos de los números de la forma n2 + 1, siendo de la forma m2 + 1. Lo cual es absurdo.

Por tanto concluimos que el enunciado es cierto.