Skip to content

Solución: ceros del factorial

by en 02/03/2014

¡Hola de nuevo!

¡Qué semana de estreno más intensa! Como sabéis, en esta ocasión nuestro acertijo estaba basado en un problema de ProgramaMe, el concurso de programación para Ciclos Formativos. En concreto, está extraído de uno de los problemas de la Final Nacional de 2012, y sus soluciones pueden comprobarse en ¡Acepta el reto!, el nuevo juez on-line que abrimos al público el martes.

Tal y como nos confirma Gualterio en su comentario, parece que nuestros lectores han preferido demostrar que sabían resolver el acertijo enviando sus propias soluciones a ¡Acepta el reto!, en lugar de ponernos los resultados de nuestras preguntas en los comentarios para no dar pistas 🙂 En el momento de escribir estas lineas, el problema ha recibido 141 envíos de 27 usuarios diferentes, 14 de los cuales lo han resuelto correctamente. ¡Enhorabuena a todos!

Para los que aún lo están intentando vamos con la explicación.

El acertijo hablaba del factorial de un número, que se define como la multiplicación de todos los números entre 1 y ese número. Así por ejemplo:

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3628800

Vemos que el factorial de 10 tiene los dos últimos dígitos a 0. La pregunta que os hacíamos era cuántos ceros tiene en la parte final el factorial de los números 13, 25, 100 y 630.

El factorial de los números crece muy deprisa, y enseguida deja pequeñas a las calculadoras. Por tanto, intentar calcular el factorial real del 25, 100 o 630 y luego contar los ceros es impráctico. Además ¡es muy aburrido para hacerlo a mano! Y, os recordamos una vez más, que aunque nuestros acertijos se puedan programar también intentamos que se puedan resolver manualmente. De modo que, como os imaginaréis, hay alguna idea oculta en el corazón del acertijo.

Para encontrarla, lo que hay que preguntarse es ¿cuándo un número tiene un cero a la derecha? La respuesta es fácil: un número tiene un cero a la derecha si es divisible por 10. Tendrá dos ceros si es divisible por 100, y así sucesivamente.

Ahora bien, para que un número sea divisible por 10 debe serlo simultáneamente por 2 y por 5 (al fin y al cabo, 2 × 5 = 10). Veamos lo que ocurre con el 10! del ejemplo:

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
10! = 2·5 × 3·3 × 2·2·2 × 7 × 2·3 × 5 × 2·2 × 3 × 2 × 1 =
10! = 7 × 52 × 34 × 28 = 3628800

Lo que hemos hecho ha sido descomponer cada número en sus factores primos, de manera que, por ejemplo, para el 9 hemos puesto 3·3. Luego hemos agrupado los números y vemos que 10! es el resultado de, entre otras cosas, multiplicar dos cincos y ocho doses. Eso significa que 10! “tiene dentro” una pareja de cincos y doses, lo que significan dos ceros al final.

Para saber el número de ceros finales del factorial de cualquier otro número hay que averiguar cuántos cincos y cuantos doses encierra. Como veis en el ejemplo, en el factorial de un número lo que “escasean” son los cincos, pues el de doses es alto (¡al menos hay uno por cada par!). De modo que en la práctica es suficiente con saber cuántos cincos guarda.

Y ¿cómo lo sabemos? ¡Fácil! Aparece un nuevo 5 cada vez que añadimos un nuevo múltiplo de 5 en el número. Por ejemplo, 5! tiene solo uno, y por tanto un único 0 al final (5!=120); 10! tiene dos (el del 5 y el del 10), y 15! tiene tres (al añadir el 15=5·3). Esto nos da la respuesta para la primera pregunta que os hacíamos. 13! no tiene ningún 5 más de los que tiene 10!, por tanto 13! tiene dos ceros al final.

Según todo esto, en principio, lo único que hay que hacer es dividir por 5 el número y ya tenemos una primera posible respuesta. ¡Hay mucha gente que empezó así en sus soluciones de Acepta el reto! 🙂 Pero hay una cosa importante más que hay que tener en cuenta. Y es que hay números que esconden varios cincos. En concreto, tras el 13 os preguntábamos por el número de ceros de 25!. Y ese caso guardaba una sorpresa, como avisó Gualterio.

¿Por qué? Porque el número 25 esconde dos cincos, pues 25=5·5. Esto significa que el número 25 añade dos cincos y por tanto dos ceros en el factorial final. Así, el 25! tiene dentro 6 cincos (5, 10, 15, 20 y dos del 25), lo que suponen 6 ceros al final. ¡Esa era la respuesta correcta!

Esto de “tener dos cincos” le ocurre a todos los múltiplos de 25, como el 50, 75 y 100. La siguiente pregunta era precisamente el número de ceros del 100. El 100 tiene 20 múltiplos de 5, y por tanto 20 ceros. Pero además, tiene 4 múltiplos de 25 que añaden un cinco más, lo que hace un total de 24 ceros al final.

¡Pero no acabamos ahí! El número 125 esconde 3 cincos (125=5·5·5) y también lo hacen todos sus múltiplos (125, 250, 375, …). Y así podemos seguir con 625 que añade 4 (625=5·5·5·5). Para la última pregunta que os hacíamos, el 630, había que tener en cuenta todo esto. En concreto, el 630 tiene dentro 126 múltiplos de 5, de los cuales 25 son además múltiplo de 25, de los que 5 son también múltiplos de 125, de los que uno es múltiplo de 625. Por tanto, el número de ceros de 630! es 126+25+5+1=157.

¡Y ya están todas las respuestas dadas! Una vez entendido el secreto del acertijo, programarlo no es difícil. Si lo haces y quieres probar tu solución, puedes hacerlo aquí. ¡Acepta el reto y sube la media de envíos correctos!

¡Hasta el próximo!

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: