Con motivo del comentario-solución de Germán Puga Castillo al problema 1 del concurso nacional de la OMM 2001 (y el feedback de Jesús Rodríguez Viorato), el problema llamó mi atención por su aparente simplicidad. Voy a comentarlo en este post (y a resolverlo apoyándome en la idea de Germán). El problema es el siguiente:
Encuentra todos los números de 7 dígitos que son múltiplos de 3 y de 7, y cada uno de cuyos dígitos es 3 o 7.
El plan obvio de solución
El plan de solución es más o menos claro: aplicar el criterio del 3 para obtener una lista de los números múltiplos de 3 (y las condiciones del enunciado) pero que incluye algunos números no múltiplos de 7. Estos se eliminarían en una segunda etapa.
Éste es el plan obvio. Sólo que la implementación de la segunda etapa presenta complicaciones pues el criterio del 7 es difícil de aplicar. Y aquí --en la implementación de la segunda etapa-- es donde entra la valiosa idea de Germán.
La lista de la primera etapa se puede clasificar --de acuerdo al criterio del 3-- en los siguientes tres clases:
- el número que no tiene ningún 7 (sus 7 dígitos son 3);
- los números que tienen 3 sietes y 4 treses;
- los números que tienen seis sietes y un tres.
Con esto ya se tiene una lista (virtual) de los números de siete cifras que son posibles --les llamaré candidatos. La primera clase está compuesta por un único candidato, los de la segunda son $C(7,4)=35$ candidatos, y los de la tercera son 7.
En total son 1+35+7=43 candidatos. Así que la tarea de verificar su divisibilidad entre 7 es totalmente factible por fuerza bruta --el único problema es generarlos, es decir, hacer la lista. Esta solución la abordaré hacia el final del post.
La idea de Germán
Otra forma de verificar tal divisibilidad (que evita construir la lista) es la de Germán. Enseguida mi edición de ella.
Representemos el candidato genérico $n$ según la notación desarrollada de potencias de 10:
$$n=a_6\times10^6+a_5\times10^5+a_4\times10^4+a_3\times10^3+a_2\times10^2+a_1\times10^1+a_0\times10^0$$
(Donde $a_i$ es un 3 o un 7.)
La idea de Germán es muy original: si $a_i=7$ (para algún i) entonces pasa la prueba en automático; de otra manera (si fuese un 3), entonces hay que considerar el residuo de $10^i$ en la división entre 7. En otras palabras, el candidato puede expresarse como 7(suma de potencias de 10)+3(suma de potencias de 10).
Y se ve que, para la verificación de la divisibilidad entre 7 de un candidato, basta considerar la suma de potencias de 10 con un tres como factor. Para eso necesitamos calcular los residuos en la división entre siete de las potencias de 10. (Notemos que las cosas se facilitan porque cada potencia apunta a la posición del dígito.)
Potencia residuo
0 1
1 3
2 2
3 6
4 4
5 5
6 1
Aplicación de la idea a los candidatos
Con esta información ya podemos hacer la verificación de la divisibilidad entre 7 de los candidatos. Empezamos con las clases 1 y 3.
Clase 1 (puros treses):
$$n=3(10^6+10^5+10^4+10^3+10^2+10^1+10^0)$$
Y se ve que los residuos de las potencias de 10 suman 22. De aquí que el residuo de $n$ en la división entre 7 es 3.
Esto se puede verificar directamente dividiendo 3333333 entre 7, lo cual se puede hacer de memoria si uno "tira a la basura" el cociente y solamente se queda con el residuo en cada paso de la división: 33, residuo 5; 53, residuo 4; 43, residuo 1; 13, residuo 6; 63, residuo 0; 3, residuo 3. Bueno, hay que saber la tabla del 7 y tener práctica en el método para hacerlo rápido.
Clase 3 (seis sietes y un tres):
En este caso hay que ver que, en la notación desarrollada, aparece un único sumando con factor 3. Digamos que sea $3\times10^k$, para algún $k$ de $\{0,1,2,3,4,5,6\}$. Pero sabemos que los residuos de $10^k$ pertenecen al conjunto $\{1,2,3,4,5,6\}$. Así que tres veces ese residuo no es nunca un múltiplo de 7.
En resumen, las clases 1 y 2 de candidatos no contienen números de 7 cifras con dígitos 3 o 7 divisibles entre 3 o 7.
Clase 2 (tres sietes y cuatro treses):
Como ya se dijo, basta considerar las 4 potencias de 10 asociadas al 3 (que tienen como factor un 3). Por tanto, de los residuos $1,1,2,3,4,5,6$ buscamos 4 que sumen un múltiplo de 7. Y aquí no hay más que generar todas las posibilidades por fuerza bruta. (Hay que enlistar y verificar.) Los generaremos en orden lexicográfico:
1123 sí
1124
1125
1126
1134
1135
1136
1145
1146
1156
1234
1235
1236
1245
1246
1256 sí
1345
1346 sí
1356
1456
1456
2345 sí
2346
2356
2456
3456
Se concluye que las posibilidades de los cuatro residuos que llevan a la divisibilidad entre 7 de los candidatos son:
1123
1256
1346
2345
Aplicación de la correspondencia entre residuos y posición
Recordemos aquí que cada residuo corresponde a una posición (a una potencia de 10) --excepto el residuo 1 que tiene dos posiciones.
| $10^i$ | $10^6$ | $10^5$ | $10^4$ | $10^3$ | $10^2$ | $10^1$ | $10^0$ |
| Residuo | 1 | 5 | 4 | 8 | 2 | 3 | 1 |
Por tanto, 1123 corresponde a 3_ _ _333, es decir, al número 3777333.
A los residuos 1256 le corresponden 2 números: 33_33_ _ y _3_33_3, es decir, 3373377 y 7373373.
De manera similar, a 1346 le corresponden dos: 3_33_3_ y _ _33_33, es decir, 3733733 y 7733733.
Finalmente, a 2345 le corresponde el número _33_33_, es decir, 7337337.
En resumen, los números buscados son:
3777333
3373377
7373373
3733737
7733733
7337337
Segunda etapa (por fuerza bruta):
No la voy a realizar completamente. Baste decir que tiene dos dificultades: la generación de los candidatos y la verificación de cada uno de ellos por división directa (tirando a la basura los cocientes). Por orden lexicográfico, los primeros 10 candidatos son:
3333777
3337377
3337737
3337773
3373377
3373737
3373773
3377337
3377373
3377733
Para 3333777, la división con cociente a la basura sería: 33, residuo 5; 53, residuo 4; 43, residuo 1; 17, residuo 3; 37, residuo 2; 27, residuo 6. Se descarta.
Para 3337377, se tiene: 33, residuo 5; 53, residuo 4; 47, residuo 5; 53, residuo 4; 47, residuo 5; 57, residuo 1. Se descarta.
Para 3337737, se tiene: 33, residuo 5; 53, residuo, 4; 47, residuo 5; 57, residuo 1; 13, residuo 6; 63, residuo 0. Se acepta.
Etcétera.
Claro que esta forma de implementar la segunda etapa es muy tediosa. Pero es factible terminarla en una hora o menos. Y es recompensante, pues ¡te llevas los 7 puntos!.
Los saluda
jmd
Muy buena pagina, estos