Problema de la moneda

Problema matemático

Con sólo monedas de 2 y 5 peniques no se pueden ganar 3 peniques, pero sí se puede ganar cualquier cantidad entera mayor.

Problema de monedas de Frobenius con monedas de 2 y 5 peniques visualizadas como gráficos:
Las líneas inclinadas denotan gráficos de 2 x + 5 y = n donde n es el total en peniques, y x e y son el número no negativo de monedas de 2 y 5 peniques, respectivamente.
Un punto en una línea da una combinación de 2 y 5 peniques para su total dado (verde).
Múltiples puntos en una línea implican múltiples combinaciones posibles (azul).
Solo las líneas con n = 1 o 3 no tienen puntos (rojo).

En matemáticas , el problema de la moneda (también conocido como el problema de la moneda de Frobenius o problema de Frobenius , en honor al matemático Ferdinand Frobenius ) es un problema matemático que pide la cantidad monetaria más grande que no se puede obtener utilizando solo monedas de denominaciones específicas . ^[1] Por ejemplo, la cantidad más grande que no se puede obtener utilizando solo monedas de 3 y 5 unidades es 7 unidades. La solución a este problema para un conjunto dado de denominaciones de monedas se llama número de Frobenius del conjunto. El número de Frobenius existe mientras el conjunto de denominaciones de monedas sea coprimo entre sí .

Existe una fórmula explícita para el número de Frobenius cuando solo hay dos denominaciones de monedas diferentes, y : el número de Frobenius es entonces . Si el número de denominaciones de monedas es tres o más, no se conoce ninguna fórmula explícita. Sin embargo, para cualquier número fijo de denominaciones de monedas, existe un algoritmo para calcular el número de Frobenius en tiempo polinomial (en los logaritmos de las denominaciones de monedas que forman una entrada). ^[2] No se conoce ningún algoritmo en tiempo polinomial en el número de denominaciones de monedas, y el problema general, donde el número de denominaciones de monedas puede ser tan grande como se desee, es NP-hard . ^{[3] [4]} ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle xy-x-y}$

Declaración

En términos matemáticos el problema se puede plantear así:

Dados números enteros positivos tales que mcd , encuentre el entero más grande que no se puede expresar como una combinación cónica entera de estos números, es decir, como una suma: ${\displaystyle a_{1},a_{2},\dots ,a_{n}}$ ${\displaystyle (a_{1},a_{2},\dots ,a_{n})=1}$ ${\displaystyle k_{1}a_{1}+k_{2}a_{2}+\dots +k_{n}a_{n}}$

donde son números enteros no negativos. ${\displaystyle k_{1},k_{2},\dots ,k_{n}}$

Este entero más grande se llama número de Frobenius del conjunto y generalmente se denota por ${\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}$ ${\displaystyle g(a_{1},a_{2},\dots ,a_{n})}$

La existencia del número de Frobenius depende de la condición de que el máximo común divisor (MCD) sea igual a 1. De hecho, las sumas potenciales son múltiplos del MCD en todos los casos. Por lo tanto, si no es 1, entonces siempre hay números arbitrariamente grandes que no se pueden obtener como sumas. Por ejemplo, si tuvieras dos tipos de monedas valoradas en 6 centavos y 14 centavos, el MCD sería igual a 2, y no habría forma de combinar cualquier número de tales monedas para producir una suma que fuera un número impar ; además, tampoco se podrían formar los números pares 2, 4, 8, 10, 16 y 22 (menores que m=24 ). Por otro lado, siempre que el MCD sea igual a 1, el conjunto de números enteros que no se puede expresar como una combinación cónica de está acotado de acuerdo con el teorema de Schur y, por lo tanto, existe el número de Frobenius. ${\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}$

Números de Frobenius para pequeñosnorte

Sólo existe una solución en forma cerrada para el problema de la moneda cuando n  = 1 o 2. No se conoce ninguna solución en forma cerrada para n  > 2. ^[4]

norte= 1

Si , entonces debemos tener para que se puedan formar todos los números naturales. ${\displaystyle n=1}$ ${\displaystyle a_{1}=1}$

norte= 2

Si , el número de Frobenius se puede encontrar a partir de la fórmula , que fue descubierta por James Joseph Sylvester en 1882. ^{[5] [nb 1]} Sylvester también demostró para este caso que hay un total de números enteros no representables (positivos). ${\displaystyle n=2}$ ${\displaystyle g(a_{1},a_{2})=a_{1}a_{2}-a_{1}-a_{2}}$ ${\displaystyle N(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)/2}$

Otra forma de la ecuación para es dada por Skupień ^[8] en esta proposición: Si y entonces, para cada , hay exactamente un par de números enteros no negativos y tales que y . ${\displaystyle g(a_{1},a_{2})}$ ${\displaystyle a_{1},a_{2}\in \mathbb {N} }$ ${\displaystyle \gcd(a_{1},a_{2})=1}$ ${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$ ${\displaystyle \rho }$ ${\displaystyle \sigma }$ ${\displaystyle \sigma <a_{1}}$ ${\displaystyle n=\rho a_{1}+\sigma a_{2}}$

La fórmula se demuestra de la siguiente manera. Supongamos que deseamos construir el número . Como , todos los números enteros para son mutuamente distintos módulo . Por lo tanto, cualquier número entero debe ser congruente módulo con uno de estos residuos; en particular, tomando hay un valor único de y un número entero único , tal que . Reordenando, tenemos un número entero no negativo tal que . De hecho, porque . ${\displaystyle n\geq (a_{1}-1)(a_{2}-1)}$ ${\displaystyle \gcd(a_{1},a_{2})=1}$ ${\displaystyle n-ja_{2}}$ ${\displaystyle j=0,1,\ldots ,a_{1}-1}$ ${\displaystyle a_{1}}$ ${\displaystyle m}$ ${\displaystyle a_{1}}$ ${\displaystyle m=a_{1}}$ ${\displaystyle j=\sigma \geq 0}$ ${\displaystyle t}$ ${\displaystyle a_{1}=n-\sigma a_{2}+ta_{1}}$ ${\displaystyle \rho =1-t}$ ${\displaystyle n=\rho a_{1}+\sigma a_{2}}$ ${\displaystyle \rho \geq 0}$ ${\displaystyle \rho a_{1}=n-\sigma a_{2}\geq (a_{1}-1)(a_{2}-1)-(a_{1}-1)a_{2}=-a_{1}+1>(-1)a_{1}}$

Para demostrar que exactamente la mitad de los números enteros son representables como combinaciones lineales de números enteros no negativos, primero se muestra que si el número entero es representable, entonces no es representable, donde . ${\displaystyle 0,1,\ldots ,ab-a-b}$ ${\displaystyle k\in [0,ab-a-b]}$ ${\displaystyle N-k}$ ${\displaystyle N=ab-a-b}$

Se demuestra entonces que la inversa también es cierta: si no es representable, entonces es representable. Para demostrarlo, se utiliza el hecho de que , lo que nos permite escribir . Reduciendo y reordenando los coeficientes añadiendo múltiplos de según sea necesario, podemos suponer (de hecho, este es el único tal que satisface la ecuación y las desigualdades). ${\displaystyle k}$ ${\displaystyle N-k}$ ${\displaystyle \gcd(a,b)=1}$ ${\displaystyle k=xa+yb}$ ${\displaystyle ab}$ ${\displaystyle 0\leq x<b}$ ${\displaystyle x}$ ${\displaystyle x}$

De manera similar, tomamos satisfactorios y . Ahora podemos agregar estas ecuaciones para escribir que, usando da como resultado . El entero es positivo, porque . De hecho, dado que el lado izquierdo de es divisible por , y , debemos tener que es divisible por . Sin embargo , entonces , de modo que . Sustituyendo esto en y restando de ambos lados da como resultado . Entonces . Esto implica que , lo que significa que exactamente uno de o es negativo. Si es negativo, entonces , lo que significa que es representable; el caso cuando es negativo implica que es representable. ${\displaystyle u,v}$ ${\displaystyle N-k=ua+vb}$ ${\displaystyle 0\leq u<b}$ ${\displaystyle N=(u+x)a+(y+v)b}$ ${\displaystyle N=ab-a-b}$ ${\displaystyle ab-b(1+y+v)=a(x+u+1)}$ ${\displaystyle x+u+1}$ ${\displaystyle x,u\geq 0}$ ${\displaystyle ab-b(1+y+v)=a(x+u+1)}$ ${\displaystyle b}$ ${\displaystyle (a,b)=1}$ ${\displaystyle x+u+1}$ ${\displaystyle b}$ ${\displaystyle x,u\leq b-1}$ ${\displaystyle x+u+1\leq 2b-1}$ ${\displaystyle x+u+1=b}$ ${\displaystyle ab-b(1+y+v)=a(x+u+1)}$ ${\displaystyle ab}$ ${\displaystyle b(1+y+v)=0}$ ${\displaystyle 1+y+v=0}$ ${\displaystyle y+v=-1}$ ${\displaystyle y}$ ${\displaystyle v}$ ${\displaystyle y}$ ${\displaystyle v\geq 0}$ ${\displaystyle N-k=ua+vb}$ ${\displaystyle v}$ ${\displaystyle k}$

Por lo tanto, para cualquier entero no negativo , sabemos que exactamente uno de o es representable (y estos son distintos, porque deben ser impares ya que los enteros son primos entre sí). Esto muestra que la mitad de los enteros en el rango dado son representables; dado que hay enteros en el rango , esto da el resultado deseado. ${\displaystyle k\in [0,ab-a-b]}$ ${\displaystyle k}$ ${\displaystyle (ab-a-b)-k}$ ${\displaystyle ab-a-b}$ ${\displaystyle a,b}$ ${\displaystyle (ab-a-b+1)=(a-1)(b-1)}$ ${\displaystyle [0,ab-a-b]}$

norte= 3

Se conocen fórmulas ^[9] y algoritmos rápidos ^{[10] para tres números, aunque los cálculos pueden ser muy tediosos si se hacen a mano.}

También se han determinado límites inferiores y superiores más simples para los números de Frobenius para n = 3. El límite inferior asintótico debido a Davison

${\displaystyle f(a_{1},a_{2},a_{3})\equiv g(a_{1},a_{2},a_{3})+a_{1}+a_{2}+a_{3}\geq {\sqrt {3a_{1}a_{2}a_{3}}}}$

es relativamente agudo. ^[11] ( aquí está el número de Frobenius modificado, que es el mayor entero no representable por combinaciones lineales de enteros positivos de ). La comparación con el límite real (definido por la relación paramétrica, donde ) muestra que la aproximación es solo 1 menos que el valor verdadero como . Se conjetura que un límite superior paramétrico similar (para valores de que son coprimos por pares y ningún elemento es representable por los otros) es donde . ${\displaystyle f}$ ${\displaystyle a_{1},a_{2},a_{3}}$ ${\displaystyle f(z(i))=9i^{2}+54i+79}$ ${\displaystyle z(i)=a_{1}a_{2}a_{3}=(3i+7)(3i+10)(3i^{2}+19i+29)}$ ${\displaystyle i\rightarrow \infty }$ ${\displaystyle a_{1},a_{2},a_{3}}$ ${\displaystyle f(z(i))=6i^{2}+19i+13}$ ${\displaystyle z(i)=a_{1}a_{2}a_{3}=(3i+2)(3i+3)(6i+7)}$

El comportamiento promedio asintótico de para tres variables también se conoce como: ^[12] ${\displaystyle f}$

${\displaystyle f(a_{1},a_{2},a_{3})\sim {\frac {8}{\pi }}{\sqrt {a_{1}a_{2}a_{3}}},}$

Conjetura de Wilf

En 1978, Wilf conjeturó que dados los números enteros coprimos , y su número de Frobenius , tenemos ${\displaystyle a_{1}<a_{2}<...<a_{d}}$ ${\displaystyle F}$

${\displaystyle d\geq {\frac {F+1}{F+1-g}},}$

donde denota el número de todos los números enteros positivos no representables. ^[13] En 2015, Moscariello y Sammartano demostraron una versión asintótica de esto. ^[14] ${\displaystyle g}$

Números de Frobenius para conjuntos especiales

Sucesiones aritméticas

Existe una fórmula simple para el número de Frobenius de un conjunto de números enteros en una secuencia aritmética . ^[15] Dados los números enteros a , d , w con mcd( a ,  d ) = 1:

${\displaystyle g(a,a+d,a+2d,\dots ,a+wd)=\left(\left\lfloor {\frac {a-2}{w}}\right\rfloor \right)a+d(a-1)}$

El caso anterior puede expresarse como un caso especial de esta fórmula. ${\displaystyle n=2}$

En el caso de que , podemos omitir cualquier subconjunto de los elementos de nuestra secuencia aritmética y la fórmula para el número de Frobenius sigue siendo la misma. ^[16] ${\displaystyle a>w^{2}-3w+1}$ ${\displaystyle a+2d,a+3d,...,a+(w-3)d,a+(w-2)d}$

Sucesiones geométricas

También existe una solución en forma cerrada para el número de Frobenius de un conjunto en una secuencia geométrica . ^[17] Dados los números enteros m , n , k con mcd( m ,  n ) = 1:

${\displaystyle g(m^{k},m^{k-1}n,m^{k-2}n^{2},\dots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}.}$

Una fórmula más simple que también muestra simetría entre las variables es la siguiente. Dados números enteros positivos , con sea . Entonces ^[18] ${\displaystyle a,b,k}$ ${\displaystyle \gcd(a,b)=1,}$ ${\displaystyle A_{k}(a,b)=\{a^{k},a^{k-1}b,\ldots ,b^{k}\}}$

${\displaystyle g(A_{k}(a,b))={\sigma }_{k+1}(a,b)-{\sigma }_{k}(a,b)-(a^{k+1}+b^{k+1}),}$

donde denota la suma de todos los números enteros en ${\displaystyle {\sigma }_{k}(a,b)}$ ${\displaystyle A_{k}(a,b).}$

Ejemplos

Números de McNuggets

Una caja de 20 McNuggets de pollo de McDonald's

Un caso especial del problema de la moneda a veces también se conoce como los números McNugget . La versión McNuggets del problema de la moneda fue presentada por Henri Picciotto, quien la colocó como un rompecabezas en Games Magazine en 1987, ^[19] y la incluyó en su libro de texto de álgebra en coautoría con Anita Wah. ^[20] Picciotto pensó en la aplicación en la década de 1980 mientras cenaba con su hijo en McDonald's, resolviendo el problema en una servilleta. Un número McNugget es el número total de McNuggets de pollo de McDonald's en cualquier número de cajas. En el Reino Unido , las cajas originales (antes de la introducción de las cajas de nuggets del tamaño de Happy Meal ) eran de 6, 9 y 20 nuggets.

Según el teorema de Schur , puesto que 6, 9 y 20 son primos entre sí (conjunto por conjunto) , cualquier número entero suficientemente grande puede expresarse como una combinación lineal (entero no negativo) de estos tres. Por lo tanto, existe un número no McNugget más grande, y todos los números enteros mayores que él son números McNugget. Es decir, todo número entero positivo es un número McNugget, con el número finito de excepciones:

1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37 y 43 (secuencia A065003 en la OEIS ).

Por lo tanto, el número no McNugget más grande es 43. ^[21] El hecho de que cualquier número entero mayor que 43 sea un número McNugget se puede ver considerando las siguientes particiones de enteros

${\displaystyle 44=6+6+6+6+20}$

${\displaystyle 45=9+9+9+9+9}$

${\displaystyle 46=6+20+20}$

${\displaystyle 47=9+9+9+20}$

${\displaystyle 48=6+6+9+9+9+9}$

${\displaystyle 49=9+20+20}$

Cualquier número entero mayor se puede obtener sumando una cierta cantidad de 6 a la partición correspondiente indicada anteriormente. Una comprobación sencilla demuestra que 43 McNuggets no se pueden comprar, ya que:

1. las cajas de 6 y 9 por sí solas no pueden formar 43 ya que solo pueden crear múltiplos de 3 (con excepción del propio 3);
2. incluir una sola casilla de 20 no ayuda, ya que el resto requerido (23) tampoco es múltiplo de 3; y
3. más de una caja de 20, complementada con cajas de tamaño 6 o mayor, obviamente no puede dar un total de 43 McNuggets.

Desde la introducción de las cajas de nuggets de 4 piezas del tamaño de Happy Meal, el número más grande que no sea un McNugget es 11. En los países donde el tamaño de 9 piezas se reemplaza por el tamaño de 10 piezas, no existe un número más grande que no sea un McNugget, ya que no se puede hacer ningún número impar.

Otros ejemplos

En rugby union , hay cuatro tipos de puntajes: goal de penal (3 puntos), drop goal (3 puntos), try (5 puntos) y try convertido (7 puntos). Al combinarlos, es posible cualquier total de puntos excepto 1, 2 o 4. En rugby sevens , aunque se permiten los cuatro tipos de puntaje, los intentos de goal de penal son raros y los drop goals son casi desconocidos. Esto significa que los puntajes de equipo casi siempre consisten en múltiplos de tries (5 puntos) y tries convertidos (7 puntos). Los siguientes puntajes (además de 1, 2 y 4) no se pueden hacer a partir de múltiplos de 5 y 7 y, por lo tanto, casi nunca se ven en sevens: 3, 6, 8, 9, 11, 13, 16, 18 y 23. A modo de ejemplo, ninguno de estos puntajes se registró en ningún juego de la Serie Mundial de Sevens 2014-15 .

De manera similar, en el fútbol americano , la única forma de que un equipo anote exactamente un punto es si se otorga un safety contra el equipo contrario cuando intenta convertir después de un touchdown (que en este caso tiene un valor de 6). Como se otorgan 2 puntos por safeties del juego regular y 3 puntos por goles de campo , son posibles todos los puntajes que no sean 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 y 7–1.

Complejidad temporal de Shellsort

El algoritmo Shellsort es un algoritmo de ordenamiento cuya complejidad temporal es actualmente un problema abierto . La complejidad del peor caso tiene un límite superior que puede darse en términos del número de Frobenius de una secuencia dada de números enteros positivos.

El menor problema del peso vivo

Las redes de Petri son útiles para modelar problemas en computación distribuida . Para tipos específicos de redes de Petri, a saber, circuitos ponderados conservativos, sería conveniente saber qué "estados" o "marcas" posibles con un peso determinado están "vivos". El problema de determinar el peso vivo mínimo es equivalente al problema de Frobenius.

Términos en potencia expandida de un polinomio

Cuando un polinomio univariante se eleva a una determinada potencia, se pueden tratar los exponentes del polinomio como un conjunto de números enteros. El polinomio desarrollado contendrá potencias mayores que el número de Frobenius para algún exponente (cuando MCD=1), p. ej., para el conjunto {6, 7} que tiene un número de Frobenius de 29, por lo que un término con nunca aparecerá para ningún valor de pero algún valor de dará términos que tengan cualquier potencia mayor que 29. Cuando el MCD de los exponentes no es 1, entonces las potencias mayores que algún valor solo aparecerán si son múltiplos del MCD, p. ej. para , las potencias de 24, 27,... aparecerán para algún valor(es) de pero nunca valores mayores que 24 que no sean múltiplos de 3 (ni los valores más pequeños, 1-8, 10-14, 16, 17, 19-23). ${\displaystyle x}$ ${\displaystyle (1+x^{6}+x^{7})^{n}}$ ${\displaystyle x^{29}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle (1+x^{9}+x^{15})^{n}}$ ${\displaystyle n}$

Véase también

• Problema con el sello postal
• Problema de generar cambios
• Monedas de plata
• Semigrupo numérico

Notas

1. La fuente original a veces se cita incorrectamente como ^[6], en la que el autor planteó su teorema como un problema recreativo ^[7] (y no declaró explícitamente la fórmula para el número de Frobenius).

Referencias

1. J. Ramírez Alfonsín (2005). El problema diofántico de Frobenius . Universidad de Oxford. Prensa.
2. Ravi Kannan (1992). "Lattice se traduce de un politopo y el problema de Frobenius". Combinatoria . 12 (2): 161-177. doi :10.1007/BF01204720. S2CID  19200821.
3. D. Beihoffer; J. Hendry; A. Nijenhuis; S. Wagon (2005). "Algoritmos más rápidos para números de Frobenius". Revista Electrónica de Combinatoria . 12 : R27. doi : 10.37236/1924 .
4. Weisstein, Eric W. "Problema de las monedas". MundoMatemático .
5. Sylvester, James Joseph (1882). "Sobre subinvariantes, es decir, semiinvariantes de la cuántica binaria de orden ilimitado". American Journal of Mathematics . 5 (1): 134. doi :10.2307/2369536. JSTOR  2369536.
6. Sylvester, James Joseph (1884). "Pregunta 7382". Preguntas matemáticas de Educational Times . 41 : 21.
7. J. Ramírez Alfonsín (2005). El problema diofántico de Frobenius . Universidad de Oxford. Prensa. pag. xiii.
8. Skupień, Zdzisław (1993). "Una generalización de los problemas de Sylvester y Frobenius" (PDF) . Acta Aritmética . LXV.4 (4): 353–366. doi : 10.4064/aa-65-4-353-366 .
9. Tripathi, A. (2017). "Fórmulas para el número de Frobenius en tres variables". Journal of Number Theory . 170 : 368–389. doi : 10.1016/j.jnt.2016.05.027 .
10. Véase el semigrupo numérico para obtener detalles de uno de estos algoritmos.
11. M. Beck; S. Zacks (2004). "Límites superiores refinados para el problema diofántico lineal de Frobenius". Adv. Appl. Math . 32 (3): 454–467. arXiv : math/0305420 . doi :10.1016/S0196-8858(03)00055-1. S2CID  119174157.
12. Ustinov, A. (2009). "La solución del problema de Arnold sobre la asintótica débil de los números de Frobenius con tres argumentos". Sbornik: Matemáticas . 200 (4): 131–160. Código Bibliográfico :2009SbMat.200..597U. doi :10.1070/SM2009v200n04ABEH004011.
13. Wilf, HS (1978). "Un algoritmo de círculo de luces para el "problema del cambio de dinero"". The American Mathematical Monthly . 85 (7): 562–565.
14. Moscariello, A. y Sammartano, A. (2015). "Sobre una conjetura de Wilf acerca del número de Frobenius". Mathematische Zeitschrift . 280 : 47–53. arXiv : 1408.5331 . doi :10.1007/s00209-015-1412-0.{{cite journal}}: CS1 maint: multiple names: authors list (link)
15. Ramírez Alfonsín, Jorge (2005). El problema diofántico de Frobenius . Prensa de la Universidad de Oxford. págs. 59–60.
16. Lee, SH; O'neill, C.; Van Over, B. (2019). "Sobre monoides numéricos aritméticos con algunos generadores omitidos". Semigroup Forum . 98 (2): 315–326. arXiv : 1712.06741 . doi :10.1007/s00233-018-9952-3. S2CID  119143449.
17. Ong, Darren C.; Ponomarenko, Vadim (2008). "El número de Frobenius de secuencias geométricas". INTEGERS: The Electronic Journal of Combinatorial Number Theory . 8 (1): A33 . Consultado el 4 de enero de 2010 .
18. Tripathi, Amitabha (2008). "Sobre el problema de Frobenius para secuencias geométricas, artículo A43". INTEGERS: La revista electrónica de teoría combinatoria de números . 8 (1).
19. Picciotto, Henri (1987). "Math McPuzzle". Games Magazine . 85 (abril/mayo): 52.
20. Wah, Anita; Picciotto, Henri (1994). "Lección 5.8 Números como bloques de construcción" (PDF) . Álgebra: temas, herramientas, conceptos . pág. 186.
21. Weisstein, Eric W. "Número McNugget". MathWorld .

Lectura adicional

• Tuenter, Hans JH (abril de 2006). "El problema de Frobenius, sumas de potencias de números enteros y recurrencias para los números de Bernoulli". Journal of Number Theory . 117 (2): 376–386. doi : 10.1016/j.jnt.2005.06.015 . MR  2213771. Zbl  1097.11010.

Enlaces externos

• Cómo pedir 43 Chicken McNuggets – Numberphile