Cuando usamos un razonamiento inductivo, debemos pensar de qué manera resolver el problema para cierto número nos permite resolverlo para uno más grande, en este caso, si sabemos pagar $n$ centavos podemos pagar $n+5$ simplemente agregando una moneda más. Escribamos esto con los detalles necesarios.
Veamos que podemos pagar todos los precios entre $44$ y $48$, estos van a ser nuestros casos base.
$44=2\cdot 12+4\cdot 5$
$45=0\cdot 12+9\cdot 5$
$46=3\cdot 12+2\cdot 5$
$47=1\cdot 12+7\cdot 5$
$48=4\cdot 12+0\cdot 5$
Ahora veamos qué pasa con los precios mayores que $48$. Supongamos que queremos pagar $n+5$ centavos, con $n\geq 44$, y sabemos cómo pagar $n$, esta será nuestra hipótesis inductiva.
Por hipótesis inductiva entonces, sabemos que existen cantidades $a$ y $b$ de monedas de $12$ y de $5$ de manera que $n=a\cdot 12+b\cdot 5$. Sólo queda observar que para pagar $n+5$ hay que agregar una moneda más de $5$ centavos, entonces logramos pagar $n+5$ centavos con $n+5=a\cdot 12+(b+1)\cdot 5$, es decir, con $a$ monedas de $12$ y $b+1$ monedas de $5$.
Porque, si seguimos la idea de agregar monedas de $5$ centavos, saber que podemos pagar $n$ centavos nos permita afirmar que podemos pagar $n+5$ centavos. Si pensamos en la metáfora de las fichas de dominó, tenemos $5$ filas distintas, cada una cuando cae empuja a la siguiente de su fila, pero entonces para que todas caigan debemos tirar el primer dominó de cada fila (es decir, los que representan los números $44$, $45$, $46$, $47$ y $48$) y así todas las fichas terminarán cayendo:
El enunciado se traduce en:
Todo $n\geq 44$ admite soluciones $x$ e $y$ enteras no-negativas en la ecuación:
$n=12x+5y$
Veamos que lo que pide el enunciado funciona para ciertos valores base:
$n=44$
$n=12.2+5.4$
Admite
$n=45$
$n=12.0+5.9$
Admite
$n=46$
$n=12.3+5.2$
Admite
$n=47$
$n=12.1+5.7$
Admite
$n=48$
$n=12.4+5.0$
Admite
Ok, vimos que existen ciertos valores de $n$ tales que estos admiten soluciones enteras no-negativas. Ahora veamos que si $n$ funciona, $n+5$ funciona también:
$n=12x+5y$
$n+5=12x+5y+5=12x+5(y+1)$
Por lo que, si $n$ funciona con enteros $x$ e $y$, $n+5$ funciona con enteros $x$ e $y+1$ y estamos.
Esto, quiere decir que, como vimos que $44$, $45$, $46$, $47$, $48$ cumplen con esto, todos los números de la forma $44+5k$, $45+5k$, $46+5k$, $47+5k$, $48+5k$ con $k\geq 0$ cumplen de igual manera.
Es decir, todos los números de la forma:
$44+5k$
$44+(5k+1)$
$44+(5k+2)$
$44+(5k+3)$
$44+(5k+4)$
con $k\geq 0$ Esto, representa que todo $n\geq 44$ cumple con lo propuesto con el ejercicio
Por $Chicken$ $Mc$ $Nuggets$ tenemos que para valores de $a$ y $b$ coprimos (como en este caso lo son $5$ y $12$), el mayor numero $n$ que no se puede expresar de la forma $n=ax+by$ con enteros no-negativos $x$ e $y$ es:
$n=ab-a-b$
Como en este caso la ecuación es: $n=12x+5y$
El mayor numero que no se puede representar de esta forma es $n=12.5-12-5=43$
Por lo que todo $n\geq 44$ puede representarse de esta forma perfectamente
Veamos que se pueden lograr fácilmente las cantidades de $44$ a $48$:
$44=4\times 5+2\times 12$
$45=9\times 5+0\times 12$
$46=2\times 5+3\times 12$
$47=7\times 5+1\times 12$
$48=0\times 5+4\times 12$
De ahí para arriba, se pueden expresar todos los números como alguno de esos cinco más algún múltiplo de $5$, por ejemplo:
$187=47+70\times 5$
$4573=48+905\times 5$
$69=44+5\times 5$
Como se puede llegar a esos cinco números, queda demostrado que se puede llegar a todos a partir de $44$.
Para los primeros cinco valores tenemos que
$44=12\times 2+5\times 4$
$45=12\times 0+5\times 9$
$46=12\times 3+5\times 2$
$47=12\times 1+5\times 7$
$48=12\times 4+5\times 0$
Ahora vamos a plantear una inducción completa. Supongamos que para $44\leq n \leq m$ con $48\leq m$ podemos pagar sin recibir vuelto, veamos que con $m+1$ también.
$m+1=m-4+5$ y como $44\leq m-4<m$ entonces podemos pagar con las mismas monedas con las que pagamos $m-4$ y agregarle una moneda de $5$.
Tiro una solución que, aunque es menos intuitiva que las posteadas, es distinta porque necesita un único caso base, y a partir de $n$ se construye el ejemplo de $n+1$.
Caso base: $44=5 \times 4+ 12 \times 2$.
Supongamos que para cierto $n$ es posible formarlo con monedas de $5$ y de $12$ centavos. Tenemos entonces $n=5x+12y$ con $x$ e $y$ enteros no negativos. Notemos que o bien $x \geq 7$ o bien $y \geq 2$, ya que de lo contrario, $5x+12y \leq 6 \times 5+ 1 \times 12=42 < 44$.
Separamos entonces en dos casos:
Si $x \geq 7$, haciendo $x'=x-7$, $y'=y+3$, nos queda $5x'+12y'=5(x-7)+12(y+3)=5x+12y+1=n+1$.
Si $y \geq 2$, haciendo $x'=x+5$, $y'=y-2$, nos queda $5x'+12y'=5(x+5)+12(y-2)=5x+12y+1=n+1$
Luego, si pudimos armar $n$, podremos armar $n+1$ y queda completa nuestra inducción $\blacksquare$
Bueno veo que nadie está subiendo la generalización demostrada (conocida como *se pone de pie* Chicken McNugget Theorem) así que acá va:
Sean $m$ y $n$ dos números coprimos, con $m>n$ veremos dos cosas:
1) Todo $k>mn-m-n$ es representable como $am+bn$ para algún par $(a,b)\in \mathbb{N}^2_0$
2) $mn-m-n$ no es representable como $am+bn$
Comentario: $0m,1m,2m,3m,\ldots ,(n-1)m$ recorre todas las congruencias módulo $n$ Demostración: Veamos que, al ser $n$ números, y hay $n$ posibles congruencias, si mostramos que no hay dos con la misma congruencia ya estamos. Sean $j\geq i$ dos números entre $0$ y $n-1$, supongamos que $mj\equiv mi\pmod n$, entonces $m(j-i)\equiv 0\pmod n$, luego podemos dividir por $m$ ambos lados ya que es coprimo con $n$, y queda que $n\mid j-i$, pero $n-1\geq j\geq i\geq 0\Rightarrow j-i<n$, luego debe pasar que $j-i=0$, demostrando lo que buscábamos.
Sabemos que los números $(n-1)m-(n-1),(n-1)m-(n-2),\ldots ,(n-1)m-0$ pasan por todas las congruencias módulo $n$. Con ver que todos esos números son mayores que $m(n-2)$ sabemos que todos serán expresables como $am+bn$ (ya que al número múltiplo de $m$ con esa congruencia le vamos sumando $n$ hasta llegar). Pero es claro que $(n-1)m-(n-1)=mn-m-n+1>m(n-2)=mn-2m$, ya que se reduce a $m>n-1$ lo cual es cierto. Ahora, si queremos representar un número congruente a $f$ en módulo $n$, encontramos el número entre $(n-1)m-(n-1)$ y $(n-1)m-0$ con esa congruencia y le sumamos $n$ hasta llegar al número deseado.
Ahora, supongamos que queremos expresar los números de la forma $cn+t$, con $0\leq t\leq n-1$. Si podemos expresarlo para algún $c$, podemos expresarlo para $c+1$, luego para todo $c$ por inducción. Sea $c_0$ el menor $c$ para el que podemos. Sabemos que es de la forma $am+bn$, pero si $b>0$, podemos restarle $n$ y la congruencia se mantiene, absurdo porque $c_0$ era el menor. Luego $c_0 n+t=am$, y sabemos que existe $a\leq n-1$ que cumple, y entre $0$ y $n-1$ es el único, luego es el menor. Por lo tanto sabemos que, el caso en el que $a=n-1$, nos deja que el menor número posible con esa congruencia es $(n-1)m$, entonces $m(n-1)-n=mn-m-n$ no se puede expresar como $am+bn$.
Luego llegamos a que todo número mayor que $mn-m-n$ es expresable como $am+bn$, y $mn-m-n$ no es expresable, luego en el caso particular del problema tenemos que $5\times 12-5-12=43$ es el mayor número que no se puede expresar como $5a+12b$.
Hola @Sandy, nadie lo está subiendo porque eso ya está subido en el apartado de Teoría del foro. Te recomiendo visitarlo porque está muy bueno. En particular te dejo el link que habla sobre el Teorema de Chicken McNugget y un corolario copado que tiene el teorema.