[BASE Cinque - Appunti di Matematica ricreativa]
conosciuto anche come "Il problema di Frobenius"
Grazie a Pietro Vitelli per aver inviato il seguente problema al Forum di BASE Cinque.
Salve, vi propongo questo problema ricreativo estrapolato del libro di Gardner: The colossal book of short puzzles and problems (2006).
Questo il problema in sintesi:
Problem 1.11 - Coins of the realm
Trovare il minor numero di monete differenti, che permettano di ottenere tutti i valori da 1 a 100, utilizzando non più di 2 monete (non necessariamente differenti).
Ossia, trovare il minor numero di interi naturali differenti, che permettano di rappresentare tutti i valori interi da 1 a 100, come somma di non più di 2 di essi.
Il problema dei francobolli 1
Supponiamo di avere soltanto due tipi di francobolli (o monete), rispettivamente da 3 cent e da 7 cent.
Altro esempio: a = 23, b = 37.
Il problema dei francobolli 2
E' una generalizzazione del precedente. I tipi di francobolli sono sempre 2 e possono valere a, b cent con MCD(a,b) = 1, cioè i valori sono primi fra loro.
Supponiamo di avere soltanto due tipi di francobolli (o monete), rispettivamente da a cent e da b cent.
Il problema dei 3 francobolli
Questa volta i tipi di francobolli sono 5 e la domanda è diversa.
Il servizio postale di una certa Nazione vuole utilizzare 5 denominazioni (valori) diverse di francobolli (espresse in numeri interi di denari) in modo che, usando non più di 3 francobolli, si possano ottenere tutti gli importi interi da 1 a 36 denari. Quali possono essere le denominazioni?
Tratto da una lettura di Victor Adamchik: "The postal service of the rebuilt Iraq wants to issue 5 denominations of stamps (in whole numbers of dinars) so that by using no more than 3 stamps on an envelope, citizens can pay for any postage from 1 dinar to 36 dinars. How can this be done?"
Il problema di Frobenius
All'inizio del 1900, Ferdinand Georg Frobenius (1849-1917) pose il seguente problema:
Dati n numeri interi positivi primi fra loro, trovare il più grande numero naturale (chiamato numero di Frobenius) che NON sia ottenibile come combinazione lineare a fattori non negativi dei numeri dati.
Sarà vero che fu lui ad inventarlo? Non lo so.
Data creazione: maggio 2007
Ultimo aggiornamento: maggio 2007
Coins of the realm
Il problema non è risultato tanto "short". Per BASE Cinque è ancora aperto.
Ecco alcuni estratti dalla discussione sul Forum.
Pietro Vitelli
Ad es. una possibile immediata soluzione è:
1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90.
Infatti con questi numeri riusciamo a rappresentare tutti i valori da 1 a 100 come somma di non più di 2 interi.
Ossia
1 = 1
2 = 2
...
25 = 20+5
...
30 = 30
...
51 = 50+1
...
100 = 90+10
Chiaramente si può fare di meglio.
Gardner riporta una soluzione, ma non è stato dimostrato che sia minima. Quindi il problema è tutt'ora aperto; almeno stando alla risposta sul libro.
Personalmente, ho scritto alcuni programmini per trovare una soluzione ottima, ma ci vorrebbe una eternità per analizzare tutte le possibili combinazioni: sono ((50^2)!)*51.
Sancho Panza
Una soluzione con 17 numeri:
1, 2, 4, 5, 6, 7, 8, 9, 13, 23, 33, 43, 53, 63, 73, 83, 93
(Non riesco a trovare di meglio.)
Seguono diversi interventi di Giobimbo, Jumpy94, Pasquale, Delfo52, etc., tutti validi ma purtroppo non risolutivi. Perciò, per ora concludo con l'ultimo messaggio di Pietro Vitelli su questo argomento.
Pietro Vitelli
Riporto la traccia originale di Gardner, e la soluzione migliore da lui riportata, poi fate voi:
Problem 1.11 - Coins of the realm
In this country at least eight coins are required to make the sum of 99 cents: a half-dollar, a quarter, two dimes, and four pennies.
Imagine yourself the leader of a small, newly independent nation.
You have the task of setting up a system of coniage based on the cent as the smallest unit.
Your objective is to issue the smallest numbers of different coins that will enable any value from 1 to 100 cents (inclusive) to be made with no more than two coins.
For example, the objective is easily met with 18 coins of the following values: 1,2,3,4,5,6,7,8,9,10,20,30,40,50,60,70,80,90.
Can you do better? Every value must be obtainable either by one coin or as the sum of two coins.
The two coins need not, of course, have different values.
La soluzione migliore, ma non è detto che sia minima, riportata da Gardner consta di 16 monete:
1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50.
Riporto la nota di Gardner seguente la soluzione: This solution is given, without proof that it is minimal, in Problem 19 of Roland Sprague's Recreation in Matematics, translated from Germany by T.H.O'Beirne.
La soluzione di Gardner non è unica, infatti lui stesso nella soluzione, riporta per curiosità anche un'altra soluzione, data da Peter Wegner, che utilizza 16 cifre e, essendo ridondante riesce a coprire da 1 a 104.
Eccola:
1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52
Anche in questo caso, escluso 52, una perfetta simmetria.
Il problema dei francobolli 1
Con a=3 e b=7, si possono formare i seguenti importi:
S = {0, 3, 6, 7, 9, 10, 12, 13, 14, 15, 16, . . .}
da cui discendono le risposte.
Il problema dei francobolli 2
...
Il problema dei 3 francobolli
1, 4, 6, 14, 15
Il problema di Frobenius
Nel 1884 Sylvester dimostrò che il numero di Frobenius per n=2 è: g(a, b) = ab − (a + b)
...
xhtml 1.1
Sito Web realizzato da Gianfranco Bo