Página 1 de 1

COFFEE: "Matías Saucedo" - Problema 1

Publicado: Sab 14 Mar, 2020 12:00 am
por COFFEE
Probar que con monedas de $5$ y $12$ centavos se puede pagar cualquier cantidad mayor o igual a $44$ centavos sin tener que recibir vuelto.

Re: COFFEE: "Matías Saucedo" - Problema 1

Publicado: Lun 16 Mar, 2020 11:37 pm
por COFFEE
Solución oficial
Spoiler: mostrar
Cuando usamos un razonamiento inductivo, debemos pensar de qué manera resolver el problema para cierto número nos perminte 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$.

¿Por qué necesitamos $5$ casos base?
Spoiler: mostrar
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:
$44 \rightarrow 49 \rightarrow 54 \rightarrow ...$
$45 \rightarrow 50 \rightarrow 55 \rightarrow ...$
$46 \rightarrow 51 \rightarrow 56 \rightarrow ...$
$47 \rightarrow 52 \rightarrow 57 \rightarrow ...$
$48 \rightarrow 53 \rightarrow 58 \rightarrow ...$

Re: COFFEE: "Matías Saucedo" - Problema 1

Publicado: Mar 17 Mar, 2020 12:03 am
por Fedex
Respuesta:
Spoiler: mostrar
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
Respuesta 2.0: (?
Spoiler: mostrar
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

Re: COFFEE: "Matías Saucedo" - Problema 1

Publicado: Mar 17 Mar, 2020 12:15 am
por Tomás Morcos Porras
Una respuesta más corta aunque menos interesante que la de @Fedex basada en los mismos principios:
Spoiler: mostrar
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$.

Re: COFFEE: "Matías Saucedo" - Problema 1

Publicado: Mié 18 Mar, 2020 2:42 pm
por Joacoini
Spoiler: mostrar
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$.

Terminada la inducción el problema esta completo

Listo @lucasdeamorin, mi deuda esta saldada.

Re: COFFEE: "Matías Saucedo" - Problema 1

Publicado: Mié 18 Mar, 2020 7:49 pm
por Turko Arias
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$.
Spoiler: mostrar
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$

Re: COFFEE: "Matías Saucedo" - Problema 1

Publicado: Mié 18 Mar, 2020 10:15 pm
por Brimix
A la respuesta 2.0 de @Fedex...
Spoiler: mostrar
Ya_Dejalo.jpg

Re: COFFEE: "Matías Saucedo" - Problema 1

Publicado: Vie 20 Mar, 2020 12:35 am
por Sandy
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$
Spoiler: mostrar
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$.

Re: COFFEE: "Matías Saucedo" - Problema 1

Publicado: Vie 20 Mar, 2020 7:37 pm
por Turko Arias
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.