COFFEE: "Matías Saucedo" - Problema 1

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
COFFEE
Mensajes: 83
Registrado: Vie 13 Mar, 2020 7:19 pm
Nivel: Exolímpico

COFFEE: "Matías Saucedo" - Problema 1

Mensaje sin leer 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.
2  
Avatar de Usuario
COFFEE
Mensajes: 83
Registrado: Vie 13 Mar, 2020 7:19 pm
Nivel: Exolímpico

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

Mensaje sin leer 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 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$.

¿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\to 49\to 54\to \ldots$
$45\to 50\to 55\to \ldots$
$46\to 51\to 56\to \ldots$
$47\to 52\to 57\to \ldots$
$48\to 53\to 58\to \ldots$
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

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

Mensaje sin leer 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
7  
This homie really did 1 at P6 and dipped.
Avatar de Usuario
Tomás Morcos Porras

COFFEE - Mención-COFFEE Matías Saucedo OFO - Mención-OFO 2020 COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Mención-FOFO 10 años OFO - Medalla de Bronce-OFO 2021
OFO - Medalla de Bronce-OFO 2022
Mensajes: 202
Registrado: Dom 13 Oct, 2019 5:04 pm
Medallas: 6
Nivel: 3
Ubicación: Córdoba, Córdoba

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

Mensaje sin leer 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$.
¿Mis intereses? Las várices de Winston Churchill.
Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años
OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

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

Mensaje sin leer 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.
2  
NO HAY ANÁLISIS.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

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

Mensaje sin leer 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$
6  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Avatar de Usuario
Brimix

OFO - Medalla de Oro-OFO 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020 OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2023 OFO - Medalla de Oro-OFO 2024
Mensajes: 97
Registrado: Dom 21 Abr, 2013 10:00 am
Medallas: 7
Nivel: Exolímpico
Ubicación: Rosario♥
Contactar:

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

Mensaje sin leer por Brimix »

A la respuesta 2.0 de @Fedex...
Spoiler: mostrar
Ya_Dejalo.jpg
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
6  
♪♫Nuestro ARG2 es nuestro ejemplo. 'Efe de equis mas one!'♫♪
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

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

Mensaje sin leer 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$.
Fallo inapelable.
Avatar de Usuario
Turko Arias

Colaborador-Varias OFO - Medalla de Plata-OFO 2016 OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 COFFEE - Jurado-COFFEE Matías Saucedo
OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi
FOFO 10 años - Jurado-FOFO 10 años OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022
FOFO 12 años - Jurado-FOFO 12 años OFO - Jurado-OFO 2023
Mensajes: 591
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 17
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

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

Mensaje sin leer 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.
2  
Fundamentalista del Aire Acondicionado

Y todo el orgullo de ser bien bilardista
Responder