Problema 4 del segundo nivel de la XXIII Olimpiada de Mayo (2017) Se dirige a una edad de: 14 años
Consideramos todos los números de 7 dígitos que se obtienen permutando de todas las maneras posibles los dígitos de 1234567.
¿Cuántos de ellos son divisibles entre 7?
Solución:
Este problema es tal vez uno de las más difíciles de solucionar que encontré ese año.
Puesto que no hay un criterio claro para abordar la divisibilidad por 7 a través de las cifras, o de su posición, debemos trabajar a partir de una estrategia que nos permita estudiar esta divisibilidad y cómo se altera cuando cambiamos una cifra por otra.
He visto la solución oficial, y la expondré más abajo, pero me parece muy raro que alguien descubriera un camino que llevara directo a esa solución.
La clave es encontrar una manera de saber de forma más o menos sencilla cómo recorrer todas las permutaciones de forma que conservemos cierta información sobre su resto al dividir por 7.
Voy a contar mi primer intento, que se reveló infructuoso.
Cuando cambias una cifra por otra en un número, la diferencia entre el número antes y después de cambiarlo es un múltiplo de 9 si son cifras consecutivas, de 99 si son cifras separadas por una posición, 999 si las separan dos posiciones, 9999 si la separación es de 3, y así sucesivamente (podemos encontrar una fórmula que nos diga que es un múltiplo de 10^n – 1).
Exactamente, si cambiamos una cifra por otra, y la diferencia entre una posición y otra es n, y la diferencia entre una cifra y otra es m, la diferencia entre los dos números resultantes será m·(10^n – 1).
Ahora, podemos estudiar los restos que producen 9, 99, 999, … , 999999 con respecto a 7.
Exactamente serán 2, 1, 5, 3, 4, 0. Ese último resultado estropea el intento, ya que va a producir dos restos repetidos (por ejemplo, si cambiamos la posición del 7 en el número 1234567 por todas las posiciones posibles, obtenemos 1234576, 1234765, 1237564, 1274563, 1734562 y 7234561, y el original y el último tienen el mismo resto, 5, ya que la diferencia entre ellos es 99999·6, que es múltiplo de 7. (Además de que, aunque los otros dos cambios modifican los restos siempre con respecto al primero, también en algunos casos lo pueden transformar en el mismo, como el caso de la primera transformación y la segunda, en la que ambos tienen el resto 0). Por lo tanto, este sistema de clasificación no es válido para saber si sólo uno de ellos es divisible por 7.
El segundo intento fue cambiar un número por el “siguiente”, es decir, producir a partir del número 1234567 los números 2134567, 1324567, 1243567, 1235467, 1234657, 1234576 y, claro, 7234561. De nuevo la cosa no acaba bien, ya que no es sencillo relacionarlos y de nuevo vuelve a aparecer un resto repetido (el de cambiar el original por el último), o puede que varios, ya que en este caso primero y sexto resultan ser múltiplos ambos de 7.
La clave, que en esta ocasión he de reconocer que no descubrí por mí mismo, si no que la leí en la solución oficial, es permutar todas las cifras del número manteniendo su posición y variando la cifra, es decir, a partir del número 1234567, obtener los números 2345671, 3456712 , 4567123, 5671234, 6712345, y 7123456. Si nos fijamos, los restos en esta ocasión sí serán diferentes, ya que el del original es 5, el primero es 6, el siguiente es múltiplo de 7, el siguiente es 1, el siguiente es 2, el siguiente es 3 y el último tiene resto 4.
¿Por qué se produce esta situación? En realidad es suficiente ver que lo que estamos haciendo es sumar 1 a cada número, así lo transformamos en el siguiente. El problema es que el 7 lo transformamos en un 8, en lugar de en un 1. Y por último, a este número le restamos 7.
Es decir, que al número original le sumamos 1111111, y después le restamos una cantidad que es múltiplo seguro de 7 (será 7, 70, 700, u otro múltiplo de 7 y de una potencia de 10), es decir, que no va a afectar esa última resta al resto al dividir por 7. Y, como el resto de dividir 1111111 entre 7 es exactamente 1, lo que va a pasar es que los siete restos de cada familia serán diferentes.
Y por lo tanto, de cada 7 permutaciones, una de ellas será múltiplo de 7 y las demás no.
Una vez que esto está claro, ya podemos hacer el cálculo final. Puesto que las permutaciones de los 7 números serán un total de 7·6·5·4·3·2·1 = 7!, la cantidad de ellos que serán múltiplos de 7 serán exactamente una séptima parte, es decir, 6·5·4·3·2·1 = 720.
