Problema delle monete
Da Wikipedia, l'enciclopedia libera.
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: , il cui massimo comun divisore è 1, trova il più grande numero N che non può essere espresso come
- per qualche intero non-negativo .
Se il massimo comun divisore non è uguale a 1 allora N non esiste, poiché solo i multipli del MCD possono essere scritti come combinazioni lineari come sopra; ma se il MCD è 1, allora N esiste. Il numero più grande trovato è chiamato a volte numero di Frobenius, mentre l'equazione Diofantea
è a volte chiamata equazione di Frobenius.
Indice |
[modifica] Soluzioni
Il problema delle monete è stato risolto per n = 1,2,3. nessuna soluzione in forma chiusa è conosciuta per n > 3.
[modifica] n = 1
Se n = 1, allora a meno che a1 = 1, ci saranno infiniti numeri di interi positivi m che non potranno essere espressi come m = a1x1 (quelli che non sono divisibili per a1).
[modifica] n = 2
Se n = 2, il numero di Frobenius può essere trovato dalla formula b = a1a2 − a1 − a2. Tale formula fu scoperta da James Joseph Sylvester nel 1884.
[modifica] n = 3
Algoritmi veloci sono conusciuti per tre numeri, anche se il calcolo può essere molto noioso se svolto manualmente.