Gimnasia mental (XXVI): la cesta y los huevos

Dos problemas muy similares a resolver utilizando el teorema chino del resto.

1.- Una cesta tiene un conjunto de huevos: si se sacan en grupos de 2, de 3, de 4, de 5 y de 6 queda siempre un huevo en la cesta. En cambio, si se sacan en grupos de 7 no queda ninguno.

2.- Otra cesta tiene un conjunto de huevos: si se sacan en grupos de 2 queda 1, si en grupos de 3 quedan 2, si en grupos de 4 quedan 3, si en grupos de 5 quedan 4, si en grupos de 6 quedan 5 y si se sacan en grupos de 7 no queda ninguno.

¿Cuál es el número más pequeño de huevos que hay en cada cesta?

Bueno, hay diferentes maneras de resolverlo, además de empleando el teorema chino del resto, del que he hablado al principio del post.

Voy poniendo algunas de ellas, incluidas las que se van proponiendo en forma de comentario a este post. 

a) La fuerza bruta, es decir, "a lo bestia”:

Para cada número entero positivo comprobamos el resto de dividirlo entre 2, 3, 4, 5, 6 y 7 hasta encontrar el menor de ellos cuyo resto sea 1 y 0 cuando se divide dicho número por 2 y 7, respectivamente, y para la primera cesta 1 cuando se divide entre 3, 4, 5 y 6, y para la segunda 2, 3, 4 y 5 cuando se divide entre 3, 4, 5 y 6, respectivamente.

Un método nada original y muy poco eficiente, pero si no tenemos ganas de pensar y con el ordenador…

Por tanto, en la primera cesta hay un número mínimo de 301 huevos y en la segunda de 119.

b) Refinando un poco la fuerza bruta:

Llamando X al número de huevos de cada una de las dos cestas, es evidente que de ambos enunciados se deduce que X es un múltiplo de 7 y, además, que es impar.

Teniendo en cuenta lo indicado anteriormente, para cada X múltiplo de 7 e impar buscamos el número entero positivo más pequeño de X cuyo resto de dividirlo entre 3, 4, 5 y 6 sea 1, para la primera cesta, y sea 2, 3, 4 y 5, respectivamente, para la segunda.

Algo mejoramos, ya que restringimos bastante los casos a examinar.

Por tanto, en la primera cesta hay un número mínimo de 301 huevos y en la segunda de 119.

c) Utilizando el mínimo común múltiplo: que es el método que propone mi tocayo Mikel en el primer comentario a este post.

El mínimo común múltiplo de 2, 3, 4, 5, 6 es: mcm(2,3,4,5,6) = 2² x 3¹ x 5¹ = 60.

Con este método seremos mucho más eficientes en la búsqueda de las soluciones.

c.1) Primera cesta: X - 1 debe ser múltiplo de 2, 3, 4, 5 y 6 y, por tanto, de 60.

Para cada X = 60Y + 1 (donde Y = 1, 2, 3…) buscamos el valor más pequeño de X que sea múltiplo de 7. Para Y = 5: X = 60 x 5 + 1 = 301, que es múltiplo de 7.

Por tanto, en la primera cesta hay un número mínimo de 301 huevos.

c.2) Segunda cesta: X + 1 debe ser múltiplo de 2, 3, 4, 5 y 6 y, por tanto, de 60.

Para cada X = 60Y - 1 (donde Y = 1, 2, 3…) buscamos el valor más pequeño de X que sea múltiplo de 7. Para Y = 2: X = 60 x 2 - 1 = 119, que es múltiplo de 7. 

Por tanto, en la segunda cesta hay un número mínimo de 119 huevos.

d) Aplicando el teorema chino del resto:

El enunciado del teorema sería algo así: si n₁, n₂, …, n_i son números enteros positivos primos entre sí (mcd(n_i,n_j) = 1 para i ¹ j) y a₁, a₂,.. a_i son números enteros, entonces el sistema de congruencias simultáneas X º a_j (mod n_j), donde 1 £ j £ i, tiene solución única módulo N (N = n₁ x n₂ x … x n_i) dada por:

Dicho esto, siendo X el número de huevos de cada una de las dos cestas, podemos plantear los siguientes sistemas de congruencias simultáneas.

d.1) Primera cesta:

X º 1 mod 2, es decir, 2 debe dividir a X - 1.

X º 1 mod 3, es decir, 3 debe dividir a X - 1.

X º 1 mod 4, es decir, 4 debe dividir a X - 1.

X º 1 mod 5, es decir, 5 debe dividir a X - 1.

X º 1 mod 6, es decir, 6 debe dividir a X - 1.

X º 0 mod 7, es decir, 7 debe dividir X - 0.

Para poder aplicar el teorema chino del resto los módulos deben ser coprimos entre sí, por lo que nos quedamos con el siguiente sistema de congruencias simultáneas:

X º 1 mod 3.

X º 1 mod 4.

X º 1 mod 5.

X º 0 mod 7.

Y ahora calculamos el valor de X de la siguiente forma:

N = 3 x 4 x 5 x 7 = 420.

N₁ = N / n₁ = 420 / 3 = 140; (N₁)^-1 = 2.

N₂ = N / n₂ = 420 / 4 = 105; (N₂)^-1 = 1.

N₃ = N / n₃ = 420 / 5 = 84; (N₃)^-1 = 4.

N₄ = N / n₄ = 420 / 7 = 60; (N₄)^-1 = 2.

X = 1 x 140 x 2 + 1 x 105 x 1 + 1 x 84 x 4 + 0 x 60 x 2 = 280 + 105 + 336 = 721 mod 420 = 301.

Comprobamos que 2 y 6 dividen a 300 y, por tanto, en la primera cesta hay un número mínimo de 301 huevos.

d.2) Segunda cesta:

X º 1 mod 2, es decir, 2 debe dividir a X - 1.

X º 2 mod 3, es decir, 3 debe dividir a X - 2.

X º 3 mod 4, es decir, 4 debe dividir a X - 3.

X º 4 mod 5, es decir, 5 debe dividir a X - 4.

X º 5 mod 6, es decir, 6 debe dividir a X - 5.

X º 0 mod 7, es decir, 7 debe dividir X - 0.

Para poder aplicar el teorema chino del resto los módulos deben ser coprimos entre sí, por lo que nos quedamos con el siguiente sistema de congruencias simultáneas:

X º 2 mod 3.

X º 3 mod 4.

X º 4 mod 5.

X º 0 mod 7.

Y ahora calculamos el valor de X de la siguiente forma:

N= 3 x 4 x 5 x 7 = 420.

N₁ = N / n₁ = 420 / 3 = 140; (N₁)^-1 = 2.

N₂ = N / n₂ = 420 / 4 = 105; (N₂)^-1 = 1.

N₃ = N / n₃ = 420 / 5 = 84; (N₃)^-1 = 4.

N₄ = N / n₄ = 420 / 7 = 60; (N₄)^-1 = 2.

X = 2 x 140 x 2 + 3 x 105 x 1 + 4 x 84 x 4 + 0 x 60 x 2 = 560 + 315 + 1.344 = 2.219 mod 420 = 119.

Comprobamos que 2 divide a 118 y 6 divide a 114 y, por tanto, en la segunda cesta hay un número mínimo de 119 huevos.