Estoy haciendo un problema de monedas donde:
En una ciudad donde sólo hay denominaciones en $6$ y $10$ . ¿Cuál es el mayor valor que esta ciudad no puede pagar?
En otro problema que me enseñó mi profesor, en el que en vez de números eran $5$ y $9$ Teníamos: $(5*9)-9-5 = 31$ que es la respuesta.
Utilizando esa misma lógica, obtendría $44$ pero el problema es que: $4*6+2*10 = 44$ ¡eso no tiene sentido!
Cualquier consejo o idea sería genial.
La fórmula que citas supone que las monedas no tienen un factor común, porque si no, no puedes hacer ningún valor que no sea divisible por ese factor común. Lo que corresponde cuando sí tienen un factor común es considerar unidades de ese factor. Así que tus monedas son $3$ y $5$ (unidades de $2$ ). El mayor número par que no se puede hacer es $(3×5-3-5)×2=14$ . Entonces como se puede hacer $16=10+6$ , $18=3×6$ , $20=2×10$ puede añadir $6$ necesarios para formar cualquier número par.
El problema general es el Problema de la moneda de Frobenius No conozco el nombre de la fórmula
Como ya se ha señalado, desde $(6,10)=2$ cualquier cantidad de dinero utilizada debe ser par. Suponiendo eso, ¿cuál es la mayor cantidad par que no se puede pagar?
Dividamos todo por $2$ de modo que consideremos monedas dobles de $3$ y $5$ valor.
El teorema 1 muestra que si $(a,b)=1$ y $c\ge(a-1)(b-1)$ entonces $ax+by=c$ tiene una solución donde $x,y\ge0$ .
Desde $(3-1)(5-1)=8$ cualquier cantidad de $8$ o superior se pueden pagar monedas dobles. Así, cualquier cantidad par mayor o igual que $16$ se puede pagar.
Desde $3\not\mid7$ y $5\not\mid7$ y $7\lt3\cdot5$ , el teorema 2 dice que sólo una de $7$ o $8$ puede tener una solución no negativa. Dado que $8$ tiene una solución no negativa, $7$ No puedo. Por lo tanto, la mayor cantidad par que no se puede pagar es $\mathbf{14}$ .
Teorema 1: Supongamos que $(a,b)=1$ y $c\ge(a-1)(b-1)$ . Entonces $ax+by=c$ tiene una solución no negativa, es decir, una en la que tanto $x$ y $y$ son enteros no negativos.
Prueba: Desde $(a,b)=1$ tenemos algunos $(u,v)$ para que $au+bv=1$ . El conjunto de todas las soluciones de $ax+by=c$ es $$ \{(cu+bk,cv-ak):k\in\mathbb{Z}\}\tag{1} $$ Así, tenemos una solución no negativa $(x,y)$ precisamente cuando hay un número entero $k$ para que $$ k\ge-cu/b\tag{2} $$ (para que $cu+bk\ge0$ ) y $$ k\le cv/a\tag{3} $$ (para que $cv-ak\ge0$ ). Por lo tanto, $ax+by=c$ tiene una solución no negativa si $$ [-cu/b,cv/a]\cap\mathbb{Z}\ne\{\}\tag{4} $$ Supongamos que no hay ningún entero en este intervalo. Esto significa que debe haber un $j\in\mathbb{Z}$ para que $$ [-cu/b,cv/a]\subset(j,j+1)\tag{5} $$ Desde $cu$ y $cv$ son números enteros, debemos tener $$ -cu/b-j >= 1/b\tag{6} $$ y $$ j+1-cv/a >= 1/a\tag{7} $$ Añadir $(6)$ y $(7)$ y multiplicando por $ab$ da $$ ab-cau-cbv\ge a+b\tag{8} $$ Desde $au+bv=1$ , $(8)$ se convierte en $$ c\le ab-a-b\tag{9} $$ Por lo tanto, si $c\ge ab-a-b+1=(a-1)(b-1)$ entonces existe un no negativa $(x,y)$ a $ax+by=c$ .
QED
Teorema 2: Supongamos que $(a,b)=1$ , $0\lt c\lt ab$ y tampoco $a\mid c$ ni $b\mid c$ . Entonces uno y sólo uno de $$ ax+by=c\tag{10} $$ y $$ ax+by=ab-c\tag{11} $$ tiene una solución no negativa.
Prueba: Tenga en cuenta que, puesto que ni $a\mid c$ ni $b\mid c$ ni $x$ ni $y$ puede ser $0$ en cualquier solución. Por lo tanto, cualquier solución no negativa debe ser una solución positiva, es decir, una en la que tanto $x$ y $y$ son enteros positivos.
Supongamos que ambos $as+bt=c$ y $au+bv=ab-c$ son soluciones positivas. Súmalas para obtener $$ a(s+u)+b(t+v)=ab\tag{12} $$ Desde $(a,b)=1$ , $(12)$ dice que $b\mid s+u$ y $a\mid t+v$ . Desde $s$ , $t$ , $u$ y $v$ son enteros positivos, debemos tener que $s+u\ge b$ y $t+v\ge a$ . Sin embargo $a(s+u)+b(t+v)\ge2ab$ lo que contradice $(12)$ .
Por lo tanto, hemos demostrado que a lo sumo uno de $(10)$ y $(11)$ puede tener un solución no negativa.
Supongamos que $(10)$ no tiene solución no negativa. Dado que $(a,b)=1$ , tenemos $(u,v)$ para que $au+bv=1$ . El conjunto de todas las soluciones de $ax+by=c$ es entonces $\{(cu+bk,cv-ak):k\in\mathbb{Z}\}$ . Por lo tanto, podemos encontrar un $(s,t)$ así que que $as+bt=c$ y $0\le s\lt b$ .
Desde $bt=c-as$ tenemos que $-ab\lt bt\lt ab$ . Desde $(10)$ no tiene una solución no negativa, debemos tener $-ab\lt bt\lt 0$ . Así, tenemos la solución no negativa $a(b-s)+b(-t)=ab-c$ .
Por lo tanto, hemos demostrado que al menos uno de $(10)$ y $(11)$ debe tener un solución no negativa.
QED
Se trata del conocido Teorema de los McNuggets de pollo para darle su nombre de la cultura pop, también conocido más formalmente como el Problema de Frobenius como escribió Ross.
Véase el Teorema de Schur que se aplica cuando el conjunto de números es relativamente primo.
En su caso, la confusión se debe a lo siguiente: La fórmula general para el caso de dos enteros: ab - a - b = (a-1)(b-1) -1 sólo es válida cuando {a,b} son coprimos. Pero {6,10} no son coprimos. Así que no sé si un resultado general se aplica en el caso.
(Nunca he visto el fórmula se le ha dado un nombre, por cierto. Sólo el teorema sobre cómo encontrar el valor máximo que no se puede formar).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Porque {6,10} no son coprimos. Así que la fórmula McNuggets/Frobenius
ab - a - bno se sostiene. Vea mi respuesta.