Problema delle monete

In matematica, un problema delle monete è ciascuna classe di problemi della forma generale:

Si hanno solo certe monete da utilizzare, diciamo monete da sette-quatloo e da dieci-quatloo (il quatloo è una moneta presente in un episodio di Star Trek). Si possono avere di ciascun taglio quante monete si vogliano; si può fare il cambio esatto per ogni numero di quatloo, oppure si possono avere tutti i numeri da una certa quantità in poi? (Nell'esempio, non c'è modo di fare il cambio di otto quatloos, ma ogni numero più grande di Q53 può essere ottenuto.) Se è possibile, qual è la sua grandezza? (questo bisogno non riguarda solo le monete, ma la stessa domanda può essere posta per francobolli, scatole, o il numero di McNugget).

Se tutte le monete sono un numero pari di quatloos, non si possono fare i cambi esatti per nessun numero dispari di quatloos; questo sarà vero anche se i tagli delle monete hanno come divisore comune tre o numeri più grandi. In un linguaggio più preciso si ha:

Dati n interi positivi: ${\displaystyle a_{1},a_{2},\dotsb ,a_{n}}$, il cui massimo comun divisore ${\displaystyle \operatorname {MCD} (a_{1},\dots ,a_{n})}$ è 1, trova il più grande numero N che non può essere espresso come

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\dotsb +a_{n}x_{n},}$

per qualche intero non-negativo ${\displaystyle x_{1},x_{2},\dotsb ,x_{n}}$.

Se il massimo comun divisore non è uguale a 1 allora ${\displaystyle N}$ non esiste, poiché solo i multipli del MCD possono essere scritti come combinazioni lineari come sopra; ma se il MCD è 1, allora ${\displaystyle N}$ esiste. Il numero più grande trovato è chiamato a volte numero di Frobenius, mentre l'equazione Diofantea

${\displaystyle b=a_{1}x_{1}+a_{2}x_{2}+\dotsb +a_{n}x_{n}}$

è a volte chiamata equazione di Frobenius.

Il problema delle monete è stato risolto per ${\displaystyle n=1,2}$. Nessuna soluzione in forma chiusa è conosciuta per ${\displaystyle n>2}$.

Se ${\displaystyle n=1}$, allora a meno che ${\displaystyle a_{1}=1}$, ci saranno infiniti numeri di interi positivi m che non potranno essere espressi come ${\displaystyle m=a_{1}x_{1}}$ (quelli che non sono divisibili per ${\displaystyle a_{1}}$).

Se ${\displaystyle n=2}$, il numero di Frobenius può essere trovato dalla formula ${\displaystyle b=a_{1}a_{2}-a_{1}-a_{2}}$. Tale formula fu scoperta da James Joseph Sylvester nel 1884.

Algoritmi veloci sono conosciuti per tre numeri, anche se il calcolo può essere molto noioso se svolto manualmente.

Identità_di_Bézout

• http://mathworld.wolfram.com/CoinProblem.html, su mathworld.wolfram.com.

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica