Problema de la moneda

El problema de la moneda (també conegut com el problema de la moneda de Frobenius o el problema de Frobenius, en honor al matemàtic Ferdinand Frobenius) és un problema matemàtic que consistix en averiguar quin és la major cantitat de diners que no pot obtindre's, utilisant solament monedes de denominacions específiques. Per eixemple, la cantitat més gran de diners que no es pot obtindre usant solament monedes de 3 i de 5 unitats és 7 unitats. La solució a este problema per a un conjunt donat de denominacions de moneda se li denomina el número Frobenius de dit conjunt. El número de Frobenius existix sempre que el màxim comú divisor del conjunt de les denominacions de moneda no siga major que 1.

Hi ha una fòrmula explícita per al número Frobenius quan només hi ha monedes de dos denominacions diferents, x i i : xy − x − i. Si el número de denominacions de moneda és tres o més, no es coneix cap fòrmula explícita; pero, per a qualsevol número fix de denominacions de monedes, hi ha un algoritme que calcula el número de Frobenius en temps polinomial (en els logaritmos de les denominacions de monedes que formen l'entrada). No es coneix cap algoritme de temps polinomial en el número de denominacions de monedes, i és NP-Hard el problema general en el qual el número de denominacions de monedes pot ser tan gran com es desige.

Definició

En térmens matemàtics, el problema pot ser establit de la següent manera:

Daus sancers positius a₁, a₂, …, a_n tal que MCD (a₁, a₂, …, a_n) = 1, trobe el major sancer que no pot ser expressat com una combinació cònica sancera d'estos números, és dir, com una suma:

k₁a₁ + k₂a₂ + ··· + k_na_n,

A on k₁, k₂, …, k_n són sancers no negatius(positius o 0).

A este número se li crida el Número Frobenius del conjunt { a₁, a₂, …, a_n }, i generalment es denota per g(a₁, a₂, …, a_n).

El requisit de que el màxim divisor comú (MCD) siga igual a 1, és necessari per a que existixca el número de Frobenius. Si el MCD no fora 1, cada sancer que no siga un múltiple de el MCD seria inexpresable com una combinació llineal, i molt manco cònica del conjunt, i per lo tant no hi hauria un número major. Per eixemple, si tinguera dos tipos de monedes valorades en 4 centaus i 6 centaus, el MCD seria 2, i no hi hauria forma de combinar qualsevol cantitat de tals monedes per a produir una suma que era un número impar. Pel contrari, sempre que el MCD siga igual a 1, el conjunt de sancers que no es poden expressar com una combinació llineal de { a₁, a₂, …, a_n } està definit segons la teorema de Schur , i per lo tant el número de Frobenius existirà.

Número de Frobenius per a menuts n

Solament existix una solució tancada per al problema de la moneda a on n = 1 o 2. No es coneix cap solució tancada per a n > 2.

n = 1

Si n = 1, llavors a₁ = 1 i tots els número natural podran formar-se. Per lo tant, no existix cap número Frobenius per a la variable 1.

n = 2

Si n = 2, el número de Frobenius es pot trobar a partir de la fòrmula $g (a_{1}, a_{2}) = a_{1} a_{2} - a_{1} - a_{2}$ . Esta fòrmula va ser descoberta per James Joseph Sylvester en 1884. Sylvester també va demostrar en este cas que hi ha un total de $N (a_{1}, a_{2}) = (a_{1} - 1) (a_{2} - 1) / 2$ número entero no representables.

Una atra forma de l'equació per a $g (a_{1}, a_{2})$ és donada per Skupień en esta proposició: Si $a_{1}, a_{2} \in ℕ$ i MCD(a_1, a_2) = 1 llavors, per a cada $n \geq (a_{1} - 1) (a_{2} - 1)$ , hi ha exactament un parell de sancers no negatius $ρ$ i $σ$ tal que $σ < a_{1}$ i $n = ρ a_{1} + σ a_{2}$ .

La fòrmula es prova de la següent manera. Supongam que desigem construir el número $m \geq (a_{1} - 1) (a_{2} - 1)$ . Tinga en conte que, des de MCD(a_1, a_2) = 1<, tots els sancers $m - j a_{2}$ per a $j = 0, 1, \dots, a_{1} - 1$ són mútuament distints a $a_{1}$ . Per lo tant hi ha un valor únic de $j$ , és dir $j = σ$ , i sancer no negatiu $ρ$ , tal que $m = ρ a_{1} + σ a_{2}$ : Per lo tant, $ρ \geq 0$ perque $ρ a_{1} = m - σ a_{2} \geq (a_{1} - 1) (a_{2} - 1) - (a_{1} - 1) a_{2} = - a_{1} + 1$ .

n = 3

Per a desenrollar un algoritme voraç es coneixen els tres números (vore Numerical semigroup per a conéixer els detalls de tals algoritmes) encara que els càlculs poden ser molt tediosos si es fan a mà. Ademés, s'han determinat els llímits inferior i superior per als números de Frobenius de n = 3. El llímit inferior propost per Davison té la formula següent

g (a_{1}, a_{2}, a_{3}) \geq \sqrt{3 a_{1} a_{2} a_{3}} - a_{1} - a_{2} - a_{3}

la qual és relativament aproximada.

Vore també

Problema de canvi de monedes

Referències

Este artícul conté una traducció derivada de «Problema de la moneda» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.