Newsgroup: it.hobby.enigmi
Titolo: Mille lire (variante per Livio)

Ciao Livio
Sono Bill Gates ed ho un problemino da porti.
Considerando che tra 20 anni dominero' il mondo e che l'euro sara'
una cacchetta in confronto al dollaro, il mio patrimonio sara' pari
a circa 10^1000 lire.
Ho deciso che tra 20 anni verro' in vacanza in Italia, e mi costruiro' un 
deposito alla Zio Paperone che sara' pieno di monetine. Allora ho pensato 
di dimettermi dalla Microsoft lasciando il posto a Balmer per occuparmi di 
problemi di monetine...
La mia curiosita' e' la seguente:
In quanti modi diversi posso cambiare un assegno da 10^1000 lire in monete 
da 500, 200, 100 e 50 lire ?
Ho dato questo problemino al mio esercito di programmatori, che stavano 
occupandosi di Windows 2001. In un mese, non sono ancora riusciti a 
rispondermi... e per questo Windows 2001 uscira' in ritardo.
Un mio amico matematico mi ha fornito la risposta in pochissimo tempo, ma 
poiche' lui usa Linux io non gli credo, comunque ho ancora il suo risultato  
(un numerone grande grande, devo dire)
Quindi, ho bisogno del tuo aiuto e del tuo concetto particolare di "brute 
force" per verificare questo risultato.
Ti prego, puoi darmi una mano ?
Grazie
Bill "Paolo Zavarise" Gates

Hi Bill,
..do you do?
Bill, non ti fidare dei matematici, quelli hanno la testa fra le nuvole!
Per loro 10^10 o 10^1000 tutto fa brodo.
Dicono che sono entrambi numeri finiti, entrambi molto minori 
di infinito, e quindi li confondono.
Per quanto sia alta la svalutazione dell'euro, non puoi pensare di
possedere piu' monetine che atomi nell'universo noto!
E mica si sono sbagliati di pochi ordini di grandezza!
Ricorda che se devi fare un lavoro da 10^100 e ne hai fatto 10^97
non sei a buon punto, sei appena all'uno per mille.
Da brute-force-man un aiuto te lo posso dare: 
licenzia quel matematico, non ha il senso della misura!
Ciao. A presto!
Livio    :o)
-- 
Posted from 
laguna.tiscalinet.it
 [195.130.224.86] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

licenzia quel matematico, non ha il senso della misura!
Secondo lui, se x sono i soldi che possiedo (x multiplo intero positivo di 
mille),
la risposta al quesito e'
((200+x)*(400+x)*(750+x))/60000000
per x=1000 la risposta che mi hanno dato e' 49...
per x=10^1000 mi hanno sparato un numero di 2993 cifre
Questi matematici... bah non hanno senso fisico, pero' sanno contare molto 
bene, meglio dei miei programmatori !
Ciao
PZ

 da 500, 200, 100 e 50 lire ?
Hi Bill,
I thought your problem!
Ti ho gia' detto che comunque non mi fiderei di
quel matematico, pero' supponiamo di avere una
miglior stima del capitale in lire di cui disporrai
tra vent'anni. Diciamo TOT con TOT grande (10^15 ?)
Ora l'importante per un forzabrutista sara' azzeccare
l'ordine di grandezza: con questa controlla il
tuo math.
Facciamo un passo nella forza bruta per dire che:
"Per qualunque combilazione di 500, 200 e 100 lire
la cui somma sia <= TOT, ci sara' il giusto numero
di 50 lire che copriranno la cifra".
Quindi il numero cercato sara' minore del prodotto
del numero delle 500 lire che ci stanno in TOT per
il num. delle 200 lire per il num. delle 100 lire.
A conti fatti diremo:  N < TOT^3/10^7
Di quanto minore? Qui il forzabrutista estrapola
qualche prova numerica e dice: Al massimo un ordine di
grandezza!  Quindi:
N =~ TOT^3/10^8
Nel caso TOT=10^15,   N=~10^37 che e' gia' un bel numero.
Se TOT=10^1000 allora N=~10^2992 che e' 'irreale'.
Lo so che il tuo math avra' un sussulto a parlare di
numeri 'irreali', ma e' solo un'altra cultura, e
"Le culture, se non si mescolano, che culture sono?"
[Jovanotti]
Sincerely
Livio
-- 
Posted from 
mta22-acc.tin.it
 [212.216.176.75] 


 N =~ TOT^3/10^8
Se non sbaglio, dovrebbe essere
N =~ TOT^3/(6*10^7) [circa]
facciamo una rappresentazione grafica
Il num. di monete da 500 puo' variare da 0 a TOT/500
Per ciascun valore in monete da 500, il numero di monete da 200 puo'
variare
da 0 a quanto basta per saturare TOT; quindi TOT/200 se non ci sono
monete
da 500, 0 se quelle da 500 saturano TOT.
Traccio sul piano cartesiano un triangolo rettangolo, con cateti sugli
assi,
base TOT/500 e altezza TOT/200.
Ogni punto (pardon, ogni quadretto unitario) interno al triangolo
rappresenta una possibile combinazione di 500 e 200.
I punti sull'ipotenusa rappresentano le condizioni di saturazione con
sole
monete da 500 e 200.
I punti sull'asse x rappresentano l'assenza di monete da 200, quelli
sull'asse y l'assenza di 500.
Il vertice sull'origine (angolo retto) rappresenta l'assenza di
entrambe.
Ora indico sull'asse z il numero di monete da 100, variabile da 0 (in
corrispondenza dell'ipotenusa del triangolo, a TOT/100 in corrispondenza
dell'angolo retto.
Ho costruito una piramide di base (TOT/500)*(TOT/200)/2
e altezza TOT/100, il cui volume
TOT^3/(500*200*100*6)
rappresenta [circa] tutte le combinazioni.
Il circa dipende dal fatto che la piramide e' a gradini.
Forse la formula del matematico di BILL (citato da Paolo Zavarise) ha
eliminato l'effetto gradini.
ciao
paolo
Sent via Deja.com 
http://www.deja.com/
Before you buy.

 per x=1000 la risposta che mi hanno dato e' 49...
Molto interessante, ora provo a ricavarmela,
se comunque ci dicessi come ha fatto ci risparmieresti la
fatica... :-)
Ciao
Andrea

fatica... :-)
Anche se inizialmente non ho ragionato in questo modo, ho trovato 
divertente arrivare alla soluzione "OTTIMIZZANDO" al limite il programma di 
Livio. 
n=0
For n1 = 0 To 2
 For n2 = 0 To 5
  For n3 = 0 To 10
   For n4 = 0 To 20
    If n1 * 500 + n2 * 200 + n3 * 100 + n4 * 50 = 1000 Then n = n + 1
   Next n4
  Next n3
 Next n2
Next n1
Print n
L'inizio del ragionamento e' il seguente...
Traduciamo in Pascal e generalizziamo, ipotizziamo subito (per evitare un 
noioso discorso di moduli e divisioni intere, comunque non troppo 
difficile) x multiplo di 1000.
n:=0;
for n1:=0 to x div 500 do
for n2:=0 to x div 200 do
for n3:=0 to x div 100 do
for n4:=0 to x div 50 do
if n1*500+n2*200+n3*100+n4*50==x then n:=n+1;
1) Fissato il numero di monete da 500, 200 e 100, il numero di monete da 50 
che porta ad una soluzione e' gia' fissato, quindi:
n:=0;
for n1:=0 to x div 500 do
for n2:=0 to x div 200 do
for n3:=0 to x div 100 do
if n1*500+n2*200+n3*100<=x then n:=n+1;
2) Liberiamoci subito dell'if, considerando ad esempio che
se x=1000 ed n1=2 e' inutile che vada a cercare soluzioni con monete da 
200.
n:=0;
for n1:=0 to x div 500 do
begin
r1:=x-n1*500;
for n2:=0 to r1 div 200 do
begin
r2:=r1-n2*200;
for n3:=0 to r2 div 100 do
n:=n+1;
end;
end;
3) Ovviamente anche il terzo ciclo non e' piu' necessario
n:=0;
for n1:=0 to x div 500 do
begin
r1:=x-n1*500;
for n2:=0 to r1 div 200 do
begin
r2:=r1-n2*200;
n:=n+r2 div 100+1;
end;
end;
4) r2 div 100 = r1 div 100-2*n2, possiamo eliminare r2
n:=0;
for n1:=0 to x div 500 do
begin
r1:=x-n1*500;
for n2:=0 to r1 div 200 do
n:=n+(r1 div 100)-2*n2+1;
end;
5) all'interno del secondo ciclo r1 div 100 e' costante, portiamolo fuori
n:=0;
for n1:=0 to x div 500 do
begin
r1:=x-n1*500;
n:=n+(r1 div 100)*(r1 div 200+1);
for n2:=0 to r1 div 200 do
n:=n-2*n2+1;
end;
6) Portiamo fuori anche il +1
n:=0;
for n1:=0 to x div 500 do
begin
r1:=x-n1*500;
n:=n+(r1 div 100+1)*(r1 div 200+1);
for n2:=0 to r1 div 200 do
n:=n-2*n2;
end;
7) Ricordando quanto vale la somma dei primi n numeri naturali 
n:=0;
for n1:=0 to x div 500 do
begin
r1:=x-n1*500;
n:=n+(r1 div 100+1)*(r1 div 200+1)-(r1 div 200)*(r1 div 200+1);
end;
... e ora viene il bello... comunque il for lo si eliminera' presto...
Ciao
Paolo Zavarise