P1 OMM 2001. Múltiplos de 3 y 7 con dígitos 3 o 7

Bueno, aquí hay algunos temas relacionados con tu solución. Una de ellas el residuo de las potencias $10^n$ módulo $7$. Como puedes observar, la potencia $10^6 \equiv 1 \pmod{7}$. Esto es un caso particular del pequeño teorema de Fermat [1], el cuál dice que $a^{p-1} \equiv 1 \pmod{p}$ para todo primo $p$ y $a$ primo relativo con $p$. Y hay un teorema aún más general, llamado el teorema de Euler [2].

Pero tu usaste algo más que eso, usaste que todos los residuos $10^n$ módulo $7$ son todos distintos para $n=0, \dots, 5$. Como consecuencia de que $7$ no divide $10^n$, entonces tampoco dividirá a los residuos 5 residuos de $10^n$, por todos los resiudos de $6$ son posibles excepto el cero (en total también son 6). Entonces, los residuos $10^n$ para $n=0, \dots 5$ son una permutación de los residuos $1, 2, \dots, 6$.  Esto ocurre, gracias a que $10$ es una raíz primitiva [3] de $7$.

Bueno, estos son teorías que generalizan las obsevaciones que hiciste aquí, pero que como quiera no te hacen la vida más fácil en el problema, sin embargo, sí te ayudan a ver más allá. Por ejemplo, es una coincidencia que 10 sea raíz primitiva de 7, de lo contrario, los residuos de $10^n$ serían muchos menos. Por ejemplo, sólo hay tres residuos distintos de las potencias de 9 módulo 7.

Espero haber respondido en la dirección que esperabas.

Saludos,

Por otro lado y regresando al problema. El único atajo que encuentro para evitar reducir el análisis de casos es el siguiente.

Como búscas $\{r_1, r_2,r_3,r_4\} \subset \{1, 2, 3, 4, 5, 6\}$  tales que $r_1+r_2+r_3+r_4$ sea múltiplo de 7 se puede reducir a buscar sólo dos número $\{r_5, r_6\} \subset \{1, 2, 3, 4, 5, 6\}$ que su suma sea múltiplo de 7. Esto debido a que si $\{r_1, r_2,r_3,r_4,r_5,r_6\}$ es una permutación de $\{1, 2, 3, 4, 5, 6\}$ tendrémos que $r_1+r_2\cdots + r_6 = 1+2+\cdots +6 = 21$ que es múltiplo de 7.

Esto es una buena reducción, ya que $\{r_5,r_6\}$ sólo puede ser $\{1,6\}, \{2,5\}$ y $\{3,4\}$.  Dando como consecuencia que las tres posibilidad para $\{r_1, r_2, r_3, r_4\}$ son las que tu encontraste.

Saludos

Hola Germán:

Está medio enredosa tu solución pero así y todo aplicaste una idea muy original. Te felicito por tu empeño y dedicación y por esa solución de un problema ¡del concurso nacional! (Y también te felicito por no tener miedo a compartir tus soluciones, por no tener miedo a cometer errores y a que éstos se publiquen.)

Ya vi que quedaste en la preselección 2012 y me imagino que vas a repetir. Yo te voy a recomendar que sigas resolviendo los fáciles del concurso nacional (los unos) y pues que pongas tus soluciones aquí en MaTeTaM para discutirlas. 

Este fin de semana voy a postear sobre ese problema que resolviste, el cual --a pesar de ser el fácil del 2001-- tiene su grado de dificultad...

PD: en tu solución dices que no hay sumas que den 7, pero yo encuentro que 1+1+2+3=7. (Lo que da lugar al número 3777333.) ¿Cómo explicas eso?

Te saluda