Igualando el resto de la división
¡Hola!
Si en el acertijo de la semana pasada sumábamos, en este toca dividir 🙂
Desde pequeños sabemos que cuando dividimos un número por otro nos da una parte entera y un resto (o residuo). Por ejemplo, si dividimos 14 entre 3, nos da 4, y de resto 2 («nos sobran 2» decíamos en primaria). Los restos de las divisiones son un tema muy estudiado por los matemáticos, y forman parte de la llamada álgebra modular, útil para gran cantidad de problemas.
Afortunadamente, para nuestro acertijo de hoy no necesitaremos saber tanto 🙂 La pregunta que os hacemos es, dada una lista de números, ¿cual es el número más grande que, al dividir a todos los números de esa lista da el mismo resto?
Por ejemplo, supongamos que la lista son los números 14, 23, 17, 32 y 122. Tenemos que buscar el mayor número cuya división por todos ellos dé el mismo resto. Si nos hacemos una tabla:
| Resto con | 14 | 23 | 17 | 32 | 122 |
|---|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 1 | 1 | 0 | 0 |
| 3 | 2 | 2 | 2 | 2 | 2 |
| 4 | 2 | 3 | 1 | 0 | 2 |
| 5 | … | ||||
Las filas muestran el resto de dividir cada uno de los números de la lista por un valor fijo. El resto de dividir por 1 siempre es 0 («da justo»); pero en el acertijo buscamos el mayor número que hace que el resto sea el mismo. Vemos que en este caso es el 3; al dividir por 3 todos los números de la lista inicial, el resto es siempre 2. Si siguiérais completando la tabla no encontraríais otro número mayor que hiciera coincidir los restos.
Un ejemplo más largo es la lista de números 701 1059 1417 2312. En ese caso, el mayor número que consigue dar el mismo resto es el 179; el resto, común a todos esos números, es 164.
Y ahora las preguntas 🙂 Empezamos con una fácil… ¿cual es el mayor número que da el mismo resto al dividir a los números 2, 4, 6 y 8?
Vamos con números más altos… ¿y 762 y 734?
Y ahora una más larga… ¿y los números 309, 165, 75, 201 y 381?
Antes de que cojáis papel, lápiz y calculadora, ahí va un aviso. En contra de lo que ocurre en otros acertijos, aquí no hay truco… Si os armáis de paciencia, podéis sacar la respuesta haciendo una tabla similar a la que os hemos puesto; en ese caso los que programéis tendréis ventaja porque podréis evitaros hacerla a mano.
Lo que hace interesante al acertijo es que en realidad hay una forma de resolverlo ¡sin hacer esa tabla! Es posible resolver a mano todas las listas que os planteamos en pocos minutos, aunque antes hay que pensar cómo 🙂 Pero si no se te ocurre nada y quieres probar suerte ¡haz la tabla y pon tu respuesta en los comentarios!
¡Ah! Y, como siempre, si lo resuelves y te gusta programar, puedes probar su solución aquí (aunque tendrás que tener cuidado, que en ese caso también puede haber números negativos).
¡Felices vacaciones y hasta la semana que viene!
Mucho por Programar 
A ver si hoy tengo algo de suerte…
Para 2, 4, 6 y 8:
DIVISOR: 2
RESTO: 0
Para 762 y 734:
DIVISOR: 28
RESTO: 6
Para 309, 165, 75, 201 y 381:
DIVISOR: 18
RESTO: 3
Pero no consigo hacerlo funcionar con números negativos. Será por la hora en la que lo resuelvo
Realizando pruebas he hallado un método para resolver esto que creo es correcto.
Veamos:
ordenamos los números de mayor a menor:
CASO DE PRUEBA 1: 14, 17, 23, 32 y 122
restamos a cada número su inmediato inferior:
17 – 14 = 3
23 – 17 = 6
32 – 23 = 9
122 – 32 = 90
hallamos el mínimo común múltiplo de los resultados:
m.c.m.(3, 6, 9, 90) = 3
y este es el divisor mayor cuyo resto da igual en todos los casos.
Si hacemos lo mismo con los demás casos resulta lo siguiente:
CASO DE PRUEBA 2: 701, 1059, 1417 y 2312
1059 – 701 = 358
1417 – 1059 = 358
2312 – 1417 = 895
m.c.m.(358, 895) = 179
RESPUESTA: 179
CASO 1: 2, 4, 6 y 8
4 – 2 = 2
6 – 4 = 2
8 – 6 = 2
m.c.m.(2) = 2
RESPUESTA: 2
CASO 2: 734 y 762
762 – 734 = 28
m.c.m.(28) = 28
RESPUESTA: 28
CASO 3: 75, 165, 201, 309 y 381
165 – 75 = 90
201 – 165 = 36
309 – 201 = 108
381 – 309 = 72
m.c.m.(36, 72, 90, 108) = 18
RESPUESTA: 18
1ºcaso–> 2,4,6 y 8
para pasar de 2 a 4 le sumamos 2
de 4 a 6 otra vez 2
y de 6 a 8 lo mismo
calculamos el máximo común divisor que es 2 por lo tanto el número que buscamos es 2.
Si dividimos 2,4,6 y 8 entre 2 el resto siempre es 0.
2ºcaso–> 734 y 762.
Para pasar de 734 al 762 le sumamos 28
el máximo común divisor de 28 es él mismo. Nuestro número es el 28, ya que si dividimos 734 y 762 entre 28 el resto es 6.
3ºcaso–> 75,165,201,309 y 381.
para pasar de 75 a 165 le sumamos 90
para pasar de 165 a 201 le sumamos 36
para pasar de 201 a 209 le sumamos 108
y para pasar de 309 a 381 le sumamos 72.
Descomponemos 90 en factores primos –>90=2x3x3x5
Descomponemos 36 en factores primos–>36=2x2x3x3
Descomponemos 108 en factores primos–>108=2x2x3x3x3
Descomponemos 72 en factores primos–>2x2x2x3x3
Calculamos su máximo común divisor que son todos los números comunes de menor exponente
en este caso sería 2x3x3=18. Si dividimos 75,165,201,309 y 381 entre 18 el resto siempre es 3.
Hooola,
Estoy de acuerdo con los resultados del resto. Mi razonamiento ha sido distinto, pero equivalente. Se basa en que si, por ejemplo, tenemos los números 762, 734 y 636, estamos buscando un número M que al dividir cada número de el resto es el mismo, luego:
762 = a * M + r
734 = b * M + r
636 = c * M + r
Podemos restar la primera ecuación y la segunda:
28 = (a-b)*M
lo que nos dice que M debe dividir a 28.
Y la primera y la tercera:
98 = (a – c)*M
que indica que también debe dividir a 98…
Se hace el mcd(28, 98) y tenemos el resultado. No hace falta considerar la resta de la segunda y la tercera porque no aporta información adicional.
Lo enviaré a la UVa uno de estos días 😉
Gracias por los acertijos semanales!