Skip to content

Solución: el mayor máximo común divisor

by en 30/03/2014

¡Hola, un domingo más!

Es hora de resolver el acertijo de la semana. En él, os preguntábamos cuál era el mayor máximo común divisor que se podría obtener entre todas las parejas de números distintos que se pueden formar con los números entre 1 y 10, 1 y 100 y 1 y 99.999. Como ejemplo, os hacíamos la tabla del máximo común divisor de todas las parejas de números entre 1 y 5, y llegábamos a la conclusión de que el mayor era el 2.

Iván nos dio su respuesta y, aunque tuvo una buena intuición, no acertó del todo. Efectivamente, el número 2 es importante en la búsqueda de la solución, pero no en la manera en la que él lo usaba… ¡Veamos la respuesta correcta!

El máximo común divisor (MCD a partir de ahora) de dos números es el mayor número que divide, con resto 0, a otros dos. Queremos conseguir el mayor MCD posible de entre todas las parejas de números (distintos) en un rango. Supongamos que el MCD buscado se consigue con dos números que llamaremos a y b, y que no sabemos cuáles son. Lo que está claro, es que el MCD divide a ambos, y por tanto:

a / MCD = p
b / MCD = q

Queremos que el MCD sea lo más alto posible, por lo que el resultado de la división debe ser lo más pequeño posible. Como los dos números de la pareja (nuestros a y b) no pueden ser iguales, entonces p y q tampoco pueden serlo. Y como deben ser lo más pequeños posible, sólo tenemos una opción, que los resultados de la división sean 1 y 2:

a / MCD = 1
b / MCD = 2

Fíjate que si p (o q) fuera 3, entonces irremediablemente el MCD sería más pequeño, y va en contra de lo que estamos buscando.

Si lo piensas un poco, para que la división entre a y b con su MCD dé como resultado 1 y 2 se debe cumplir que:

b = 2 × a

Es decir, que de nuestra pareja de números, uno será el doble que el otro por lo que el mayor deberá ser par. Y de hecho, el MCD será la mitad de ese número mayor. Esto es importante, porque dado que lo que queremos es conseguir el mayor MCD, tendremos que buscar en el rango el mayor número par; y la mitad será el MCD que nos están pidiendo.

¿Qué significa esto? Que la solución al acertijo es, simplemente, la mitad del número mayor del rango, teniendo cuidado si es un impar, para hacer división entera 🙂 El resultado es que las soluciones a nuestras tres preguntas eran 5, 500 y 49.999.

Iván intuyó que el número 2 era importante, y ¡así es! Pero no se pueden usar las potencias. De hecho, su solución no era válida para el ejemplo… Con la tabla, vimos que el mayor MCD era el 2, y sin embargo, la mayor potencia de 2 entre 1 y 5 es el 4 (2²) 🙂 ¡Seguro que el próximo lo resuelves bien!

Mientras llega, podéis programar la solución y probarla aquí.

¡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: