Problema de monedas
Con monedas de solo 2 peniques y 5 peniques, no se pueden ganar 3 peniques, pero se pueden generar cantidades integrales mayores.
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.
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 monedas, existe un algoritmo que calcula el número de Frobenius en tiempo polinomial (en los logaritmos de las denominaciones de monedas 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-duro .[3] [4]
Este entero más grande se llama 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 se pudo formar. 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 de acuerdo con el teorema de Schur , y por lo tanto el número de Frobenius existe.
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]
