El problema de la moneda (también conocido como el problema de la moneda de Frobenius o el problema de Frobenius , en honor al matemático Ferdinand Frobenius ) es un problema matemático que solicita la mayor cantidad monetaria que no se puede obtener utilizando solo monedas de denominaciones específicas . [1] Por ejemplo, la mayor cantidad que no se puede obtener usando solo monedas de 3 y 5 unidades es de 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 siempre que el conjunto de denominaciones de monedas no tenga un divisor común mayor que 1.
Con solo monedas de 2 peniques y 5 peniques, no se pueden ganar 3 peniques, pero se pueden generar cantidades integrales mayores.
Hay una fórmula explícita para el número Frobenius cuando sólo hay dos diferentes denominaciones de monedas, x y Y : xy - xy . Si el número de denominaciones de monedas es tres o más, no se conoce una fórmula explícita; pero, para cualquier número fijo de denominaciones de moneda, existe un algoritmo que calcula el número de Frobenius en tiempo polinomial (en los logaritmos de las denominaciones de moneda que forman una entrada). [2] Ningún algoritmo conocido es el 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]
Declaración
En términos matemáticos, el problema se puede plantear:
- Dados los números enteros positivos a 1 , a 2 , ..., a n tales que mcd ( a 1 , a 2 , ..., a n ) = 1, encuentre el entero más grande que no se puede expresar como una combinación cónica de números enteros de estos números, es decir, como una suma
- k 1 a 1 + k 2 a 2 + ··· + k n a n ,
- donde k 1 , k 2 , ..., k n son enteros no negativos.
Este entero más grande se llama el número de Frobenius del conjunto { a 1 , a 2 , ..., a n }, y generalmente se denota por g ( a 1 , a 2 , ..., a n ).
El requisito de que el máximo común divisor (MCD) sea igual a 1 es necesario para que exista el número de Frobenius. Si el MCD no fuera 1, entonces a partir de algún número m, las únicas sumas posibles son múltiplos del MCD; cada número después de m que no sea divisible por el MCD no se puede representar mediante ninguna combinación lineal de números del conjunto. [5] Por ejemplo, si tuvieras dos tipos de monedas valoradas en 6 centavos y 14 centavos, el GCD sería igual a 2, y no habría forma de combinar ninguna cantidad de tales monedas para producir una suma que fuera un número impar ; Además, los números pares 2, 4, 8, 10, 16 y 22 (menos de m = 24 ) tampoco pudieron formarse. Por otro lado, siempre que el MCD es igual a 1, el conjunto de enteros que no se puede expresar como una combinación cónica de { a 1 , a 2 , ..., a n } está acotado según el teorema de Schur , y por lo tanto el número de Frobenius existe.
Números de Frobenius para n pequeña
Existe una solución de forma cerrada para el problema de la moneda solo cuando n = 1 o 2. No se conoce una solución de forma cerrada para n > 2. [4]
n = 1
Si n = 1, entonces a 1 = 1 para que se puedan formar todos los números naturales. Por tanto, no existe ningún número de Frobenius en una variable.
n = 2
Si n = 2, el número de Frobenius se puede encontrar a partir de la fórmula. Esta fórmula fue descubierta por James Joseph Sylvester en 1882, [6] aunque la fuente original a veces se cita incorrectamente como, [7] en la que el autor planteó su teorema como un problema recreativo [8] (y no estableció explícitamente la fórmula para el número de Frobenius). Sylvester también demostró para este caso que hay un total de enteros no representables (positivos).
Otra forma de la ecuación para lo da Skupień [9] en esta proposición: Si y entonces, para cada , hay exactamente un par de números enteros no negativos y tal que y .
La fórmula se demuestra como sigue. Supongamos que deseamos construir el número. Tenga en cuenta que, dado que, todos los enteros por son módulos mutuamente distintos . Por tanto, existe un valor único de, decir y un entero no negativo , tal que : En efecto, porque .
n = 3
Las fórmulas [10] y los algoritmos rápidos [11] son conocidos 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
es relativamente nítido. [12] (aquí está el número de Frobenius modificado, que es el mayor entero no representable por combinaciones lineales de enteros positivos de.) Comparación con el límite real (definido por la relación paramétrica, dónde ) 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 pares-coprime y ningún elemento es representable por los demás) es dónde .
El comportamiento promedio asintótico de para tres variables también se conoce: [13]
Números de Frobenius para juegos especiales
Secuencias aritméticas
Existe una fórmula simple para el número de Frobenius de un conjunto de enteros en una secuencia aritmética . [14] Dados los números enteros a , d , w con mcd ( a , d ) = 1:
La El caso anterior puede expresarse como un caso especial de esta fórmula.
En 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. [15]
Secuencias geométricas
También existe una solución de forma cerrada para el número de Frobenius de un conjunto en una secuencia geométrica . [16] Dados los números enteros m , n , k con mcd ( m , n ) = 1:
- Una fórmula más simple que también muestra simetría entre las variables es la siguiente. Dados números enteros positivos , con dejar . Entonces [17]
- dónde denota la suma de todos los enteros en
Ejemplos de
Números de McNugget
Un caso especial del problema de las monedas a veces también se denomina números de McNugget . La versión McNuggets del problema de las monedas fue presentada por Henri Picciotto, quien la incluyó en su libro de texto de álgebra en coautoría con Anita Wah. [18] 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 de 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 pepitas del tamaño de Happy Meal ) eran de 6, 9 y 20 pepitas.
Según el teorema de Schur , dado que 6, 9 y 20 son primos relativos , cualquier número entero suficientemente grande puede expresarse como una combinación lineal (no negativa, entera) de estos tres. Por lo tanto, existe un número que no es McNugget más grande, y todos los enteros más grandes que él son números McNugget. Es decir, cada entero positivo es un número de 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 ).
Total | 0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|---|
+0 | 0: 0 , 0 , 0 | 1: - | 2: - | 3: - | 4: - | 5: - |
+6 | 6: 1 , 0 , 0 | 7: - | 8: - | 9: 0 , 1 , 0 | 10: - | 11: - |
+12 | 12: 2 , 0 , 0 | 13: - | 14: - | 15: 1 , 1 , 0 | dieciséis: - | 17: - |
+18 | 18: 3 , 0 , 0 | 19: - | 20: 0 , 0 , 1 | 21: 2 , 1 , 0 | 22: - | 23: - |
+24 | 24: 4 , 0 , 0 | 25: - | 26: 1 , 0 , 1 | 27: 3 , 1 , 0 | 28: - | 29: 0 , 1 , 1 |
+30 | 30: 5 , 0 , 0 | 31: - | 32: 2 , 0 , 1 | 33: 4 , 1 , 0 | 34: - | 35: 1 , 1 , 1 |
+36 | 36: 6 , 0 , 0 | 37: - | 38: 3 , 0 , 1 | 39: 5 , 1 , 0 | 40: 0 , 0 , 2 | 41: 2 , 1 , 1 |
+42 | 42: 7 , 0 , 0 | 43: - | 44: 4 , 0 , 1 | 45: 6 , 1 , 0 | 46: 1 , 0 , 2 | 47: 3 , 1 , 1 |
+48 | 48: 8 , 0 , 0 | 49: 0 , 1 , 2 | 50: 5 , 0 , 1 | 51: 7 , 1 , 0 | 52: 2 , 0 , 2 | 53: 4 , 1 , 1 |
+54 | 54: 9 , 0 , 0 | 55: 1 , 1 , 2 | 56: 6 , 0 , 1 | 57: 8 , 1 , 0 | 58: 3 , 0 , 2 | 59: 5 , 1 , 1 |
Un posible conjunto de combinaciones de cajas para un total de 0 a 59 pepitas. Cada triplete denota el número de cajas de 6 , 9 y 20 , respectivamente. |
Por lo tanto, el número más grande que no es McNugget es 43. [19] El hecho de que cualquier entero mayor que 43 sea un número McNugget se puede ver considerando las siguientes particiones enteras
Se puede obtener cualquier número entero más grande agregando un número de 6 a la partición apropiada anterior.
Alternativamente, dado que y , la solución también se puede obtener aplicando una fórmula presentada para antes: [ dudoso ]
Además, una verificación sencilla demuestra que 43 McNuggets de hecho no se pueden comprar, ya que:
- las cajas de 6 y 9 por sí solas no pueden formar 43, ya que solo pueden crear múltiplos de 3 (con la excepción de 3 en sí);
- incluir una sola casilla de 20 no ayuda, ya que el resto requerido (23) tampoco es un múltiplo de 3; y
- más de una caja de 20, complementada con cajas de tamaño 6 o más grandes, obviamente no puede dar lugar a un total de 43 McNuggets.
Desde la introducción de las cajas de pepitas del tamaño de Happy Meal de 4 piezas, el número más grande que no es McNugget es 11. En los países donde el tamaño de 9 piezas se reemplaza por el tamaño de 10 piezas, no hay un número más grande que no sea McNugget ya que no se puede hacer ningún número impar.
Otros ejemplos
En rugby union , hay cuatro tipos de puntajes: gol de penalti (3 puntos), drop goal (3 puntos), try (5 puntos) y try convertido (7 puntos). Al combinar estos puntos, es posible obtener un total de puntos excepto 1, 2 o 4. En el rugby a siete , aunque se permiten los cuatro tipos de puntajes, los intentos de gol de penalti son raros y los goles de caída casi desconocidos. Esto significa que las puntuaciones del equipo casi siempre consisten en múltiplos de try (5 puntos) y try convertido (7 puntos). Las siguientes puntuaciones (además de 1, 2 y 4) no se pueden hacer a partir de múltiplos de 5 y 7, por lo que casi nunca se ven en sietes: 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 Seven 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. Como se otorgan 2 puntos por los profundos del juego regular y 3 puntos por los tiros de campo , todas las puntuaciones excepto 1–0, 1–1, 2–1, 3–1, 4–1, 5–1 y 7– 1 son posibles.
Aplicaciones [20]
Complejidad del tiempo de Shellsort
El algoritmo Shellsort es un algoritmo de clasificación cuya complejidad temporal es actualmente un problema abierto . La complejidad del caso más desfavorable tiene un límite superior que se puede dar en términos del número de Frobenius de una secuencia dada de números enteros positivos.
Problema de peso vivo mínimo
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 conservadores , uno quisiera saber qué posibles "estados" o "marcas" con un peso dado están "vivos". El problema de determinar el menor peso vivo es equivalente al problema de Frobenius.
Términos en el poder expandido de un polinomio
Cuando un polinomio univariado se eleva a alguna potencia, se pueden tratar los exponentes del polinomio como un conjunto de números enteros. El polinomio expandido contendrá potencias de mayor que el número de Frobenius para algún exponente (cuando MCD = 1), por ejemplo, para el conjunto es {6, 7} que tiene un número de Frobenius de 29, por lo que un término con nunca aparecerá por ningún valor de pero algún valor de Dará términos que tengan algún poder de mayor que 29. Cuando el MCD de los exponentes no es 1, las potencias mayores que algún valor solo aparecerán si son un múltiplo del MCD, por ejemplo, para , potencias de 24, 27, ... aparecerán para algunos valores de pero nunca valores mayores de 24 que no sean múltiplos de 3 (ni valores menores, 1-8, 10-14, 16, 17, 19-23).
Ver también
- Problema de sello postal
- Problema de cambio
- Acuñación de Sylver
- Semigrupo numérico
Referencias
- ^ J. Ramírez Alfonsín (2005). El problema Diofantino de Frobenius . Universidad de Oxford. Prensa.
- ^ Ravi Kannan (1992). "Lattice se traduce de un politopo y el problema de Frobenius". Combinatorica . 12 (2): 161-177. doi : 10.1007 / BF01204720 . S2CID 19200821 .
- ^ 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 .
- ^ a b Weisstein, Eric W. "Problema de monedas" . MathWorld .
- ^ número de antiFrobenius
- ^ Sylvester, James Joseph (1882). "Sobre subinvariantes, es decir, semi-invariantes a la cuantica binaria de un orden ilimitado". Revista Estadounidense de Matemáticas . 5 (1): 134. doi : 10.2307 / 2369536 . JSTOR 2369536 .
- ^ Sylvester, James Joseph (1884). "Pregunta 7382" . Preguntas matemáticas de la época educativa . 41 : 21.
- ^ J. Ramírez Alfonsín (2005). El problema Diofantino de Frobenius . Universidad de Oxford. Prensa. pag. xiii.
- ^ Skupień, Zdzisław (1993). "Una generalización de los problemas de Sylvester y Frobenius" (PDF) . Acta Arithmetica . LXV.4 (4): 353–366. doi : 10.4064 / aa-65-4-353-366 .
- ^ Tripathi, A. (2017). "Fórmulas para el número de Frobenius en tres variables" . Revista de teoría de números . 170 : 368–389. doi : 10.1016 / j.jnt.2016.05.027 .
- ^ Consulte semigrupo numérico para obtener detalles de uno de estos algoritmos.
- ^ M. Beck; S. Zacks (2004). "Límites superiores refinados para el problema diofántico lineal de Frobenius". Adv. Apl. Matemáticas . 32 (3): 454–467. arXiv : matemáticas / 0305420 . doi : 10.1016 / S0196-8858 (03) 00055-1 . S2CID 119174157 .
- ^ 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 .
- ^ Ramírez Alfonsín, Jorge (2005). El problema diofántico de Frobenius . Prensa de la Universidad de Oxford. págs. 59–60.
- ^ Lee, SH; O'neill, C .; Van Over, B. (2019). "Sobre monoides numéricos aritméticos con algunos generadores omitidos". Foro de Semigroup . 98 (2): 315–326. arXiv : 1712.06741 . doi : 10.1007 / s00233-018-9952-3 . S2CID 119143449 .
- ^ Ong, Darren C .; Ponomarenko, Vadim (2008). "El número de secuencias geométricas de Frobenius" . INTEGERS: La revista electrónica de teoría de números combinatorios . 8 (1): A33. Archivado desde el original el 29 de diciembre de 2016 . Consultado el 4 de enero de 2010 .
- ^ Tripathi, Amitabha (2008). "Sobre el problema de Frobenius para secuencias geométricas, artículo A43". INTEGERS: La revista electrónica de teoría de números combinatorios . 8 (1).
- ^ Wah, Anita; Picciotto, Henri (1994). "Lección 5.8 Números de bloques de construcción" (PDF) . Álgebra: Temas, Herramientas, Conceptos . pag. 186.
- ^ Weisstein, Eric W. "Número McNugget" . MathWorld .
- ^ J. Ramírez Alfonsín (2005). El problema Diofantino de Frobenius . Universidad de Oxford. Prensa. págs. 132-135.
enlaces externos
- Cómo pedir 43 McNuggets de pollo - Numberphile