Coins of the realm (M.Gardner)

[Admin]

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.

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$

mi viene in mente il principio dei cassetti, ma niente di più

Aspetto le vostre elucubrazioni...
vel aggiornamenti sul problema.

Ciao
Admin

[giobimbo]

Vogliamo abbeverarci alle sorgenti a quanto pare, caro buon vecchio zio Martin! Considerato che il problema è stato presentato dal Gardner una quarantina d'anni fa, il fatto che sia ancora insoluto significa che non dipende dalla capacità di programmare di Admin o dalla potenza del computer, altrimenti qualcuno l'avrebbe già risolto. Mi domando se Pietro ci farebbe la gentilezza di mettere le soluzioni da lui trovate, diciamo da n=2 a n=15, chissà che esaminando tali dati a qualcuno venga l'ispirazione di un metodo, una scorciatoia, con cui affrontare la cosa in modo nuovo.

[Admin]

Mi domando se Pietro ci farebbe la gentilezza di mettere le soluzioni da lui trovate, diciamo da n=2 a n=15

Cosa intendi per "da n=2 a n=15"?
il programma che ho realizzato, in teoria controlla tutte le combinazioni che si possono ottenere;
as es. la prima combinazione presa sotto esame è:

1 = 1+0
2 = 2+0
3 = 3+0
4 = 4+0
...
99 = 99+0
100 = 100+0

in questa combinazione vengono utilizzate 100 cifre per rappresentare i numeri da 1 a 100; è il peggior caso possibile;

la successiva combinazione analizzata è:

1= 1+0
2 = 1+1
3 = 3+0
...
...
99 = 99+0
100 = 100+0

e cosi via...

ora la soluzione migliore trovata da questo programma è formata da 91 cifre! (dopo 1 ora di esecuzione).
Invece con un altro programma che analizza le combinazioni scegliendole in modo casuale, la migliore soluzione che ho trovato (sempre dopo un'ora di esecuzione) è formata da 53 cifre

Per cui, siccome la soluzione di esempio che ho postato all'inizio, ne ha 18, ho interrotto le esecuzioni dei miei programmini.

Se volete, posto la soluzione riportata da Gardner.

Ciao
Admin

[delfo52]

ipotesi di lavoro:
e se invece che solo con monete, nel reame di MG avessero corso legale anche le cambiali ?
a parte imprecisioni di tecnica bancaria, intendo dire "monete negative". Ad esempio se esistesse una moneta da "meno 1" potrei usarla per arrivare a 4 aggiungendola ad una moneta da 5...........
non so se ciò può condurre a risultati "migliori" nel senso di un sistema monetario con meno pezzature, ma perchè non provare ?

[delfo52]

affrontando il problema in modo più "sistematico", osservo che
1 ci deve essere
se non mettiamo il 2, che non è di per sè necessario, dobbiamo però mettere il 3, e, di questo passo, tutti i numeri pari saranno esclusi, ma tutti i dispari saranno necessari
se mettiamo il 2, potremo evitare di coniare il 3 e il 4, ma occorrerà il 5 e di seguito sarà necessario un numero sì e due no (1-2-5-8-11....)
prolungando la sequenza di "monete piccole consecutive", cambierà l'intervallo tra i termini successivi (es.: 1-2-3-4-5-11-17-23-29....)
La soluzione presentata da Admin è ridondante: se abbiamo le monete da 1 a 10, quella da 20 è inutile (10+10), per cui potremo coniare quella da 21, poi quella da 32-43-54-65-76-87, ma occorrerà pur sempre la 18esima da 98 euro, con cui fare acquisti fino a 108 con solo due pezzi
Coniando la serie delle monetine fino a 9, e poi 19-29-39...89, con 17 pezzi arriviamo a 99

per ora basta

[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.)

[Admin]

Ciao delfo,
la soluzione riportata da Gardner consta di 16 pezzi, e non è dimostrato che sia minima.

Siccome non mi va di procedere per tentativi, sto cercando di capire se sia possibile fare una cernita di tutte le $(50^2!)\cdot 51$ combinazioni, ossia se possiamo escludere un buon numero di combinazioni che sicuramente non possono rappresentare una soluzione ottima per il problema.

Penso che la soluzione ottima contenga valori compresi tra 1 e 50, (massimo 60);
ad es. il valore 95 che utilità darebbe ad una soluzione, se non quella di rappresentare gli ultimi numeri rimasti, che non possono essere rappresentati con gli altri valori già scelti?

Voglio provare a scartare tutte le combinazioni di somme che utilizzano valori superiori a 50;
vediamo cosa ne viene fuori...

Ciao
Admin

[Admin]

Bene,
ho scartato tutte le combinazioni che utilizzano numeri superiori a 50.
Adesso le combinazioni rimaste da analizzare sono $25^2!\,\cdot\,26$ ,
che sono all'incirca la radice quadrata del numero di combinazioni iniziali.

Ho apportato le modfiche al mio programmino, che ora è in esecuzione;
al momento ha analizzato 78.000.000 di combinazioni;
best result: 38 pezzi.
Siamo ancora lontani da risultati apprezzabili.

Bisognerebbe scartare qualche altra combinazione;
idee?

Ciao
Admin

[Br1]

Siccome non mi va di procedere per tentativi...

Sì, son d'accordo con Pietro.
Mi sembra che sia molto più interessante
trovare un sistema, un metodo, per
ricercare le soluzioni di questo problema.
Mi sembra anche che ci sia qualche buono
spunto nelle idee di Enrico.

idee?

Per il momento, nessunissima...

[giobimbo]

Per n=2 intendevo:
Trovare il minor numero di monete differenti, che permettano di ottenere tutti i valori da 1 a 2, utilizzando non più di 2 monete (non necessariamente differenti).

Ci sono due diverse soluzioni:
n=2 --> {1,1} {1,2}

Per n=3 intendevo:
Trovare il minor numero di monete differenti, che permettano di ottenere tutti i valori da 1 a 3, utilizzando non più di 2 monete (non necessariamente differenti).

C'è una sola soluzione:
n=3 --> {1,2}
E così via fino a n=15. Qua sotto, un possibile esempio di quello che Pietro potrebbe scrivere (una fatica da sobbarcarsi solo se lo ritiene utile):


1,1 - 1,2

1,2

1,1,3 - 1,2,2 - 1,2,3 - 1,2,4

...

...

[Admin]

Ciao giobimbo,
mi devi scusare, ma non riesco a seguirti;

Ci sono due diverse soluzioni:
n=2 --> {1,1} {1,2}

intendi forse n=2 --> {1} {1,2} ?

C'è una sola soluzione:
n=3 --> {1,2}

Perchè? c'è anche la soluzione {1,2,3} e la soluzione {1,3}.

Comunque, se non ho capito male, tu vuoi analizzare un certo numero di sottoproblemi (da n=1 a n=15; il problema iniziale è invece n=100) e per ognuno di essi trovare la soluzione ottima (minimo numero di valori).

Si, dovrei apportare qualche piccola modifica al programma.
Più tardi provo e posto eventualmente i risultati.

Salvo, che non abbia mal interpretato.
Fammi sapere...

Ciao
Admin

[giobimbo]

No, no, ho fatto confusione io, sto passando una settimana balorda a causa dell'insonnia.
M'interessano le soluzioni minime, cioè:
n=2 -->{1}
n=3 -->{1,2} {1,3}
...
Ripeto, solo se ti sembra possa essere utile, visto anche che devi modificare il programma. Ciao.

[Jumpy94]

Credo di aver trovato una dimostrazione al fatto che non possiamo avere un numero di monete minore di 15, come 14, al problema di Gardner. Non so se i calcoli sono esatti, ma almeno ci provo
Chiamo $k$ il numero di monete ed $n$ la cifra che desidero ( in questo caso $n=100$). Ora chiamo $C_{k,2}=\frac{k!}{2(k-2)!}$ il numero di coppie che posso avere con le $k$ monete. Ovviamente ad ogni coppia corrisponde un numero ( nel problema si fa la loro somma ). Non tutti i numeri trovati (e quindi le coppie) sono da considerare (voglio dire che alcuni di essi possono essere maggiori di $n$) per cui ci sarà una parte da scartare che chiamo $S$ e sarà uguale : $S=C_{k,2} - (n-k)$, dove ovviamente il secondo fattore indica le coppie (quindi i numeri) che vengono considerati. Facendo opportune semplificazioni (i calcoli li ho svolti in DERIVE in quanto non sono ancora pratico del calcolo fattoriale ) risulterà: $S=\frac{k^2+k-2n}{2}$. Poiché non avrebbe senso parlare di scarti negativi, si deve verificare $S>0$, ovvero $\frac{k^2+k-2n}{2}>0$. La disequazione risolta per $k$ ci da : $k\frac{1+\sqrt{1+8n}}{2}$. Posto nel nosto caso $n=100$ si ha: $k14.6509717$. $k$ è un numero naturale per cui $k>14$. Ciò mi porta a dire che la soluzione con 15 monete esiste (calcoli permettendo).


Ciao.

[Pasquale]

C'è una cosa che non mi è chiara: se è possibile ottenere 2 con due 1, allora occorrono 2 monete da 1, che sempre due sono e non una (è giusto?).
Mi piace il modo come Jumpy ha inteso di avere indicazioni circa il numero minimo di monete necessario, anche se mi pare di aver capito che bisognerebbe considerare le combinazioni con ripetizione, se è vero che si può usare 2 volte la stessa moneta, e bisognerebbe considerare pure che un numero può essere rappresentato da una sola moneta e non necessariamente da due.

[Admin]

... per cui ci sarà una parte da scartare che chiamo $S$ e sarà uguale : $S=C_{k,2} - (n-k)$

perchè è $(n-k)$ il numero di coppie considerate?

C'è una cosa che non mi è chiara: se è possibile ottenere 2 con due 1, allora occorrono 2 monete da 1, che sempre due sono e non una (è giusto?)

La soluzione cercata riguarda solo il valore delle monete, non le occorrenze delle stesse.
Una moneta va conteggiata una sola volta in una soluzione.

Ciao
Admin