Página principal › Índice multilingüe del archivo › Problema de la moneda

Problema de la moneda

problema de la moneda (también referido como Problema de la moneda de Frobenius o Problema de Frobenius) es a matemáticas el problema se asoció al matemático alemán Ferdinand Georg Frobenius e introducido a menudo en el contexto de realizar el cambio exacto dado la disponibilidad de las monedas de denominaciones específicas.

En términos matemáticos el problema puede ser indicado:

N dada números naturales con el divisor común más grande 1, encuentra el número natural más grande que puede no exprésese como combinación no negativa del número entero de estos números de n.

Para un sistema dado este número más grande se refiere como el número de Frobenius . La existencia de tal número de Frobenius se liga firmemente a la condición y sigue de Teorema de Schur.

Determinación del número de Frobenius para arbitrario n se sabe para ser NP-duro.^[1]

Números de Frobenius para pequeño n

Una solución del closed-form existe para el problema de la moneda solamente donde n=1,2 o 3. No se sabe ninguna solución del closed-form para n>3. ^[2][3]

n = 1

Si n = 1, entonces a₁ = 1 para poder formar todos los números naturales. Por lo tanto ningún número de Frobenius en una variable existe.

n = 2

Si n = 2, el número de Frobenius se puede encontrar del fórmula g(a₁,a₂) = a₁a₂ − a₁ − a₂. Este fórmula fue descubierto cerca James José Sylvester en 1884.^[4] Sylvester también demostró para este caso que hay un total de N(a₁,a₂) = (a₁ − 1)(a₂ − 1) / 2 números enteros no-representables.

n = 3

Los algoritmos rápidos se saben para tres números, aunque los cálculos pueden ser muy aburridos si están hechos a mano. Además, límites más bajos y superiores para n Se han determinado = 3 números de Frobenius. El Frobenius-tipo un límite más bajo debido a Davidson

se divulga para ser relativamente agudo.^[5]

Ejemplos

Números de McNugget

Un caso especial del problema de la moneda a veces también se refiere mientras que el “McNugget numera”. Un número de McNugget es el número total de McDonald's pollo McNuggets en cualquier número de cajas. Las cajas de la original (antes de la introducción del Comida feliz- las cajas clasificadas de la pepita) estaban de 6, 9, y 20 pepitas.

Según Teorema de Schur, desde 6, 9, y 20 son relativamente primeros, cualquier número suficientemente grande se pueden expresar como combinación linear de estos números. Son relativamente primeros porque 6=2*3, 9=3*3, y 20=2*2*5, haciendo 1 el divisor común más grande. Por lo tanto, existe un número más grande del non-McNugget, y todo numera más grande que es números de McNugget.

El número más grande del non-McNugget es 43.^[6] El hecho de que cualquier número de McNuggets más en gran parte de 43 puede ser comprado, puede ser considerado considerando eso

44 = 6 + 9 + 9 + 20

45 = 9 + 9 + 9 + 9 + 9

46 = 6 + 20 + 20

47 = 9 + 9 + 9 + 20

48 = 6 + 6 + 9 + 9 + 9 + 9

49 = 9 + 20 + 20

y que cualquier número más grande de McNuggets puede ser pedido agregando el número derecho de cajas de 6 a la combinación apropiada arriba.

Además, un cheque directo demuestra que poder de 43 McNuggets de hecho no cómprese, como:

1) las cajas de 6 y 9 solos no pueden formar 43 mientras que éstas pueden crear solamente múltiplos de 3 (a excepción de 3 sí mismo);

2) incluyendo una sola caja de 20 no ayuda, pues el resto requerido (23) no es también un múltiplo de 3; y

3) más de una caja de 20, complementada con las cajas del tamaño 6 o más grande, no puede conducir obviamente a un total de 43 McNuggets.

Los números son todos de McNugget números naturales excepto los números 1, 2, 3, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 22, 23, 25, 28, 31, 34, 37, y 43 del non-McNugget (secuencia A065003 en OEIS).

Otros ejemplos

Otro caso existe para unión del rugbi: hay cuatro tipos de cuentas: meta de la pena (3 puntos), meta de la gota (3 puntos), intento (5 puntos) e intento convertido (7 puntos). Combinando total de estos cualquier puntos es posible excepto 1, 2 o 4.

Semejantemente, en fútbol americano cada cuenta es posible excepto 1. La única manera de anotar 1 punto está DESPUÉS de una cuenta de 6 puntos. 2 puntos de una seguridad, y 3 de metas del campo significan que el resto de los números son posibles.

Referencias

1. ^ D. Beihoffer, J. Hendry, A. Nijenhuis, y S. Carro: Algoritmos más rápidos para los números de Frobenius.
2. ^ Eric W. Weisstein, Problema de la moneda en MathWorld.
3. ^ Michael Spivey, residuos cuadráticos y el Frobenius acuñan problema.
4. ^ J.J. Sylvester, pregunta 7382, preguntas matemáticas a partir de los tiempos educativos, 37 (1884) p.26.
5. ^ M. Cuba de tintura y S. Zacks, límites superiores refinados para el problema linear de Diophantine de Frobenius; Adv. Appl. Matemáticas. 32 (2004) P. 454 - 467.
6. ^ Eric W. Weisstein, Número de McNugget en MathWorld.

Acoplamientos externos