Skip to content

Solución: igualando el resto de la división

by en 31/03/2013

¡Hola!

Ha llegado el día de dar la respuesta al acertijo de la semana 🙂 Gracias a todos los que habéis puesto vuestras soluciones. ¡Esta vez sí estaban bien! Además, Borja, María y Gualterio no sólo han dado la solución, sino que han contado el proceso para resolverlo sin tanteo.

Aprovechando que nosotros podemos extendernos más, explicaremos con más calma la solución, que en los comentarios es incómodo dar los detalles y las descripciones puede ser un poco crípticas para los que no hayan pensado con calma el acertijo. Nuestra explicación será paso a paso, sin utilizar notación matemática, para intentar que cualquier lector sea capaz de entenderla. ¡Eso hará que sea un poco larga! La notación matemática es mucho más condensada que el lenguaje natural 🙂 En cualquier caso, ¡enhorabuena y gracias por vuestras explicaciones a todos los que habéis comentado en la entrada del acertijo!

Os preguntábamos cuál era el mayor número que, al dividir a todos los de una determinada lista, daba el mismo resto (o residuo). Os pusimos como ejemplo una lista, y una tabla con los restos de dividir cada número por varios divisores, hasta encontrar el que hacía que todos los restos fueran iguales.

Pero os avisábamos de que la gracia del ejercicio era resolverlo sin hacer esa tabla. ¡Vamos allá!

La primera lista que teníais que resolver era muy fácil: 2, 4, 6, y 8. Salta a la vista que todos los números son pares, por lo que todos son divisibles por 2, lo que significa que el resto da 0. Por tanto, claramente la respuesta es 2, cuyo resto es 0 con todos los números. Quizá te preguntes si no podría haber un número mayor que 2 con el que todas las divisiones tengan el mismo resto. No lo hay. Si pruebas con 3 y 4, verás que los restos no coinciden. Con 5, el resto de 2/5 es 2 y el de 4/5 es 4, y será así para cualquier número a partir de 5, por lo que los restos no volverán a coincidir nunca.

La segunda lista era más corta, con sólo dos números, pero que eran más altos. En concreto, eran los números 762 y 734. Para averiguar el número más alto que da el mismo resto con ambos números podemos empezar a probar. De nuevo, vemos que ambos son pares, por tanto el 2 da el mismo resto, 0. Pero no podemos quedarnos ahí; ¿hay algún número mayor que 2 con el que ambos números compartan el resto? Si probamos con 3, 762 / 3 da resto 0, pero 734 / 3 da 2, por lo que no nos sirve. Por otro lado, si dividimos por 4, en ambos casos el resto es 2, por lo que también es candidato a ser la respuesta correcta.

Podríamos seguir subiendo y probando, pero surge la gran pregunta, ¿cuando dejamos de buscar? Es decir, ¿hasta qué número miramos? Gracias a la la primera lista (2, 4, 6 y 8) hemos llegado a la conclusión de que basta con llegar al segundo número más pequeño (al 4), pues a partir de él los restos de la división de esos dos primeros números no coincidirán nunca. Probar a mano todos los números hasta el 762 es muy aburrido… y ya sabéis que intentamos que nuestros acertijos se puedan hacer más o menos deprisa sin utilizar un ordenador. Por tanto, ¿cuál es la manera más rápida de conseguir el número que estamos buscando?

Para resolver esta pregunta hay que pensar un poco en qué son la división y el resto realmente. Si dividimos, por ejemplo, 13 entre 5 nos da 2 y resto 3. Eso significa que podemos escribir

13 = 5 · 2 + 3

Hagamos lo mismo con los dos números de nuestra lista, 762 y 734, al dividirlos por 2 y 4, que generaban los restos iguales:

  • 762 entre 2 tiene resto 0. Podemos escribir 762 = 381 · 2 + 0
  • 734 entre 2 tiene también resto 0: 734 = 367 · 2 + 0
  • 762 entre 4 tiene resto 2. Podemos escribir 762 = 190 · 4 + 2
  • 734 entre 4 tiene también resto 2: 734 = 183 · 4 + 2

Si sigues buscando, verás que ni el 5 ni el 6 generan el mismo resto. Pero el 7 vuelve a conseguirlo:

  • 762 entre 7 tiene resto 6. Podemos escribir 762 = 108 · 7 + 6
  • 734 entre 7 tiene también resto 6: 734 = 104 · 7 + 6

Fíjate que al aumentar el divisor (primero 2, luego 4 y finalmente 7) los cocientes se han ido haciendo más pequeños y acercando. Cuando dividimos por 2 obtuvimos 381 y 367; por 4 fueron 190 y 183; por 7 fueron 108 y 104. Aunque en principio no parezca resultar muy útil, vamos a restar los dos números (762 y 734), tal y como propuso Gualterio en los comentarios, y ver cómo quedan:

  • 762 – 734 = (381·2 + 0) – (367·2 + 0) = 381·2 – 367·2 = (381-367)·2 = 14·2
  • 762 – 734 = (190·4 + 2) – (183·4 + 2) = 190·4 – 183·4 = (190-183)·4 = 7·4
  • 762 – 734 = (108·7 + 6) – (104·7 + 6) = 108·7 – 104·7 = (108-104)·7 = 4·7

Fíjate que los restos de las divisiones de cada divisor han desaparecido al restar. Tenemos que la resta de los dos números de la secuencia 762-734 podemos escribirla como la multiplicación de un número (diferente cada vez) por 2, o por 4, o por 7, que son los números que habíamos encontrado que daban el mismo resto al usarlos para dividir a ambos números. Si intentas escribir 762-734 con una multiplicación usando el 3, el 5 o el 6 (que no daban el mismo resto para ambos números) no lo conseguirás (salvo que uses números decimales, pero eso no nos sirve 🙂 ).

Durante todo este tiempo estamos buscando el dividendo mayor, es decir preferimos el 4 al 2, y el 7 al 4. Y ahora llegamos a la pregunta del acertijo, ¿cual es el mayor número que podemos conseguir que dé el mismo resto con 762 y 734? Para responderlo, fíjate que al ir creciendo el divisor (2, 4, 7) el otro multiplicando se va haciendo cada vez más pequeño (14, 7, 4). Si queremos conseguir el divisor más grande posible, tendremos que usar en ese otro multiplicando el número más pequeño posible, y ese número es el 1. Es decir, estamos buscando:

762 – 734 = 1 · mejorNúmero

Y entonces, ¿cuál es el número más alto que al dividir a 762 y a 734 da el mismo resto? ¡Efectivamente! ¡La resta de los dos, es decir 28!

  • 762 = 27 · 28 + 6
  • 734 = 26 · 28 + 6

Fíjate que los cocientes de las divisiones (27 y 26) no pueden estar más cerca, como habíamos anticipado. Si lo piensas un poco, te darás cuenta de que no tiene sentido buscar números más altos al 28, es decir a la resta de los dos números, como divisores candidatos; todos ocasionarán restos distintos.

Antes de seguir, vamos a pensar lo que ha pasado aquí… en concreto, ¿qué tienen de particular el 2, el 4 y el 7 con el 28, para que también dieran el mismo resto, y por qué no ocurría lo mismo con el 3? ¡Fácil! Tanto 2 como 4 son divisores exactos de 28. Sin embargo, 3 no lo es. Si dividimos 762 y 734 por 28, obtenemos un resto común, pero también lo hacemos si dividimos por cualquiera de sus divisores exactos (2, 4, 7 y 14), aunque no son la respuesta correcta por ser más pequeños.

¿Qué hemos aprendido por tanto con la lista 762 y 734? Que si tenemos sólo dos números en la lista, el mayor número que al dividir a ambos da el mismo resto es su resta. Además, todos los números que dividen a esa resta también dan el mismo resto al dividir a los números iniciales ¡Son dos conclusiones muy importantes!

La última pregunta era para una lista de números más larga, 309, 165, 75, 201 y 381.

Si la lista fuera únicamente el 309 y el 165, ahora sabemos, sin tener que hacer la tabla, que el mayor número que ocasiona el mismo resto es el 144 (=309-165). Efectivamente, para ambos números el resto al dividirlos por 144 da 21.

Pero si dividimos los demás números de la lista por 144 el resto no es 21. Si cogemos los 5 números en parejas y calculamos sus restas, obtenemos muchos valores: 144, 234, 108, 72, 90, 36, 216, 126, 306 y 180. ¡Ni siquiera se repite algún número! ¿Cuál es entonces el número que da el mismo resto para todos los números de la lista a la vez?

Como vimos antes, si el 144 da el mismo resto para 309 y 165, también dan el mismo resto todos los números que dividen al 144, como el 2, 3, 4, 8, 9, … Con eso en mente, el número que estamos buscando es el mayor número que divide a todas las restas simultáneamente. Y eso es el famoso máximo común divisor que nos enseñaban en el cole (y no el mínimo común múltiplo, que aquí Borja se equivocó al ponerle el nombre :-)). Si recuerdas cómo se hacía (María M.P. lo planteó rápidamente en su solución), puedes calcularlo. Si  no, puedes ayudarte de sitios como éste. En ambos casos llegarás al mismo resultado: el máximo común divisor de los números 144, 234, 108, … etcétera es 18. Ese es el máximo valor que al dividir a todos los números de la lista original da el mismo resto, 3.

Si eres de los que te gusta programar, para calcular el máximo común divisor puedes usar el que quizá sea el algoritmo más antiguo de la humanidad: el algoritmo de Euclides. Es una forma mucho más cómoda de calcularlo que la alternativa tradicional de sacar los factores primos comunes ¡incluso si lo tienes que hacer a mano! Si tienes curiosidad por “verlo” puedes pasarte por aquí.

Y como siempre, si programas la solución para el acertijo, puedes probarla aquí. En ese caso ten cuidado con los números negativos. Aunque los hemos ignorado todo el tiempo, al dividir los números 762 y 734 por -28 también se consigue el mismo resto, pero ese número es más pequeño que 28 y por tanto no es la solución que buscamos. Cuando saques la diferencia de dos números acuérdate de quedarte con su valor absoluto para evitar problemas 🙂

¡Este acertijo ha sido intenso! El de mañana será más fácil. ¡Hasta entonces!

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: