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.
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!)\cdot 51$
![Shocked :shock:](./images/smilies/icon_eek.gif)
mi viene in mente il principio dei cassetti, ma niente di più
Aspetto le vostre elucubrazioni...
vel aggiornamenti sul problema.
Ciao
Admin