Selectivo Cono Sur - 2014 - Problema 1

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 759
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Selectivo Cono Sur - 2014 - Problema 1

Mensaje sin leer por Gianni De Rico » Sab 05 May, 2018 5:14 pm

Spoiler: mostrar
Tenemos $N=10m+c\equiv k(31)\Rightarrow -3(10m+c)\equiv -3k(31)\Rightarrow m-3c\equiv -3k(31)$
Esto nos dice dos cosas:
$(1)$: Si $N$ no es múltiplo de $31$, entonces $m-3c$ tampoco lo será, en particular, $m-3c\neq 0\forall m,c$
$(2)$: Si $N$ es múltiplo de $31$, entonces $m-3c$ también lo será

Por $(1)$ vemos que si un número cumple entonces es múltiplo de $31$

Ahora veamos que todos los múltiplos de $31$ cumplen. Comprobamos a mano que $N=31x$ con $1\leqslant x\leqslant 9$ cumplen (es fácil, pues luego del primer paso el resultado es $0$). Vamos a demostrar con inducción fuerte que todos los múltiplos de $31$ cumplen.
Sea $N=31k$ con $k\geqslant 10$, supongamos como hipótesis inductiva que todos los múltiplos positivos de $31$ anteriores cumplen. Como $N\geqslant 31\cdot 10$ tenemos que $m\geqslant 31$, y como $0\leqslant c\leqslant 9$ tenemos $0\leqslant 3c\leqslant 27$. Luego, $m>3c\Rightarrow m-3c>0$. Es decir que $m-3c$ es positivo, pero por $(2)$ tenemos que $m-3c$ es múltiplo de $31$. Luego, es un múltiplo de $31$ positivo y menor que $N$, por lo tanto cumple y llegará a $0$ en una cantidad finita de pasos. Luego, $N$ llega a $0$ en una cantidad finita de pasos. La inducción está completa.

Entonces probamos que si un número cumple es múltiplo de $31$, y si es múltiplo de $31$ cumple. Luego, $N$ cumple si y sólo si es múltiplo de $31$
[math]

Responder