Skip to content

Solución: escribiendo la descomposición en factores primos

by en 16/06/2014

Hola!

Tras una semana con el acertijo a la espera de vuestras soluciones, llega la hora de desvelar las respuestas correctas y cómo las hemos conseguido nosotros. En esta ocasión os contábamos que todos los números tienen una única descomposición en factores primos, pero que recolocando los factores el número de formas de escribir cada descomposición varía. Por ejemplo:

6 = 2 × 3 = 3 × 2
12 = 2 × 2 × 3 = 2 × 3 × 2 = 3 × 2 × 2

lo que indica que la descomposición de 6 se puede escribir de 2 formas, y la de 12 de 3. Os preguntábamos por los números más pequeños cuya descomposición en factores primos puede escribirse, exactamente, de 6, 10 y 45 formas. En los comentarios, Ferrán nos dio su solución para 10 y 45 formas y ¡era correcta! incluso aunque nuestro planteamiento del acertijo no era del todo claro y tenía dudas. Os retamos con una pregunta más, 72 formas, y Gualterio la contestó también correctamente. ¡Enhorabuena a ambos! Curiosamente, nadie contestó a la primera pregunta, la de 6 formas…

Veamos cómo resolvimos nosotros el acertijo. Si vuestra solución es diferente, ¡no dudéis en contárnosla!

El primer paso es analizar por qué la descomposición en factores primos del 6 se puede escribir de 2 formas y, después, por qué la de 12 se puede escribir de 3. Para eso, nos apoyamos en la rama de las matemáticas denominada combinatoria que ya ha aparecido en algún otro acertijo. En el caso que nos ocupa, si miramos la descomposición del número 6 vemos que tenemos dos números primos distintos (el 2 y el 3) y queremos saber de cuántas formas diferentes podemos colocarlos. Dicho de otro modo, ¿de cuántas formas puedo colocar n elementos? Esa pregunta la responden las permutaciones. No es muy difícil llegar a la fórmula matemática de… n! o, “factorial de n” que es la multiplicación de todos los números entre 1 y n.

El caso del 12 es más complicado, porque hay factores repetidos. Debido a ello, el concepto de permutación no nos sirve directamente, y hay que complicarlo un poco más con las permutaciones con repetición. De nuevo, volviendo a las matemáticas, si tenemos n elementos, donde hay a iguales entre sí, otros b iguales entre sí, etcétera (con todos ellos sumando n) entonces el número de formas de colocarlos (o sea, las permutaciones con repetición) son:

PR^{a,b,\ldots}_n= {n! \over a!\cdot b! \cdot \ldots}

Con esto, analizamos lo que ocurre con el número 12. Su descomposición en factores primos tiene tres números (2 × 2 × 3), por lo que n es 3. Además, hay dos que se repiten, por lo que a=2 y b=1. Por tanto:

PR^{2,1}_3= {3! \over 2!\cdot 1! \cdot \ldots} = {6 \over 2} = 3

Esto significa que las matemáticas nos dicen que la descomposición de 12 la podemos poner de 3 formas diferentes, tal y como vimos escribiendo a mano todas las opciones.

Vamos ahora con las preguntas. La primera era ¿cuál es el número más pequeño cuya descomposición en factores primos se puede escribir de 6 formas? Es decir, estamos buscando los valores de n, a, b, … tales que:

PR^{a,b,\ldots}_n= {n! \over a!\cdot b! \cdot \ldots} = 6

Esto no tiene una solución sencilla, por lo que nos dedicaremos a tantear. Pero en lugar de ponernos a hacerlo ciegamente, empezaremos descomponiendo en factores primos el número 6, para que su “radiografía” nos dé una pista de con qué números empezar a probar. En concreto, sabemos que 6 = 2 × 3.

Además, nos vamos a apoyar en la descomposición en factores de los factoriales. Por ejemplo:

2! = 2
3! = 3 × 2
4! = 4 × 3 × 2 = 23 × 3
4! = 5 × 4 × 3 × 2 = 23 × 3 × 5

Si lo hacemos con más números, terminaremos sacando la siguiente tabla, donde mostramos el número de veces que aparece cada número primo en los factores de cada factorial (hasta 10):

2 3 5 7
2! 1
3! 1 1
4! 3 1
5! 3 1 1
6! 4 2 1
7! 4 2 1 1
8! 7 2 1 1
9! 7 4 1 1
10! 8 4 2 1

La tabla indica que, por ejemplo, 6! = 24 × 32 × 51

Mirando esta tabla y lo que queremos conseguir:

PR^{a,b,\ldots}_n= {n! \over a!\cdot b! \cdot \ldots} = 6 = 2 \cdot 3

es fácil llegar a la conclusión de que:

6 = 2 \cdot 3 = {3! \over 1! \cdot 1! \cdot 1!}

De aquí, podemos deducir que el número más pequeño cuya descomposición tiene 6 formas de escribirse tiene tres factores diferentes (por los tres unos en el denominador). Para que el número sea lo más pequeño posible, cogemos los factores (primos) más pequeños posibles y por tanto la respuesta es:

21 × 31 × 51 = 30

La segunda pregunta era el número más pequeño cuya descomposición se puede escribir de 10 formas. Sabemos que:

10 = 2 × 5

y queremos escribirlo de la forma:

PR^{a,b,\ldots}_n= {n! \over a!\cdot b! \cdot \ldots} = 10 = 2 \cdot 5

Éste es un poco más complicado, de modo que vamos más despacio. Para el n! del numerador necesitamos encontrar un factorial que incluya en su descomposición un 2 y un 5. Para eso, recurrimos a nuestra tabla y vemos que 5! es 23 × 3 × 5. Por comodidad, representaremos sólo los exponentes, por lo que diremos que 5! es (3, 1, 1). Por su parte, 10 lo representaremos como (1, 0, 1) pues su descomposición es 21×30×51.

Fijaos que en este caso el factorial de 5 incluye más factores que 10, y hay que “quitarlos” dividiendo por a!, b!, etcétera. En concreto, si “restamos” la representación del 5! (3, 1, 1) y del 10 (1, 0, 1) nos queda (2, 1). Tenemos que conseguir esa descomposición usando factoriales para ponerlos en el denominador. Mirando en la tabla, es fácil ver que eso se consigue con 3! y con 2! de modo que ¡ya lo tenemos!:

PR^{3,2}_5= {5! \over 3!\cdot 2!} = 10 = 2 \cdot 5

Es importante asegurarse de que los números del denominador suman lo mismo que el numerador, es decir que n = a + b + …. En este caso esto se cumple. Lo único que falta es sacar el número de la respuesta. Cualquier número que tenga dos factores primos diferentes, uno elevado al cubo (por el 3!) y otro al cuadrado (por el 2!) tendrá exactamente 10 formas de escribir su descomposición. Como queremos el más pequeño, usamos los primos más bajos, y eso nos da:

23 × 32 = 72

tal y como nos dijo Ferrán en los comentarios 🙂

Vamos con el último, el 45 = 3 × 3 × 5. Igual que antes, ésto lo representamos como (0, 2, 1). Fíjate que empezamos con un 0 porque el 2 (el primer número primo) no aparece en la descomposición. Ahora necesitamos buscar en nuestra tabla de la descomposición de factoriales el primero que incluya dos treses y un cinco. Ese resulta ser 6! (4, 2 1). Ahora necesitamos buscar una forma de “quitar” los cuatro doses y para eso la única opción es poner en el denominador cuatro 2!:

PR^{2,2,2,2}_6= {6! \over 2!\cdot 2! \cdot 2! \cdot 2!} = 45

Pero… ¡¡cuidado!! Esta solución no sirve, porque la suma de los denominadores (2+2+2+2) es mayor que el numerador (6) y por tanto no es una fórmula válida para las permutaciones sin repetición. Por tanto hay que probar con un número mayor en el numerador. El problema es que al subir a 7! nos aparece un primo más en la lista que tendremos que quitar, dejando de todos modos los dos treses y el cinco de la descomposición del 45. Analizando la tabla y haciendo pruebas mentalmente, veréis que la única opción válida es:

PR^{8,2}_{10} = {10! \over 8!\cdot 2!} = 45

El número que estamos buscando, por tanto, es 28 × 32 que es 2304, como también nos dijo Ferrán.

Si utilizáis la misma técnica, veréis que la última pregunta que os hacíamos en los comentarios, 72, tiene como respuesta 1920, tal y como nos dijo Gualterio.

Tened en cuenta que nos hemos tomado algunas licencias con las respuestas, porque las preguntas que os hicimos estaban escogidas con cuidado. En realidad en ocasiones no es suficiente con encontrar la primera forma de escribir el número original, sino que es necesario seguir subiendo. Por ejemplo:

720 = {6! \over 1! \cdot 1! \cdot 1! \cdot 1! \cdot 1! \cdot 1!} = {10! \over 7! \cdot 1! \cdot 1! \cdot 1!}

Por tanto, cualquier número con 6 factores diferentes tendrá 720 formas de escribir su descomposición, y, al mismo tiempo, cualquier número con 10 factores de los cuales 7 son el mismo (y los demás son distintos) también. Resulta que con la primera configuración (6 diferentes) el número más pequeño es el 30.030, pero con la segunda (10 factores, 7 de ellos iguales) es el 13.440, que es más pequeño y por tanto preferible. En ninguna de nuestras preguntas ocurre eso (aunque todos se pueden escribir de más formas usando numeradores mayores). No obstante, que pueda ocurrir hace más difícil programar una solución. Pero si te atreves, siempre podrás probarla aquí 🙂

Este ha quedado muy matemático… en el próximo intentaremos compensarlo 🙂

Chao!

Anuncios

From → Soluciones

Dejar un comentario

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: