Newsgroup: it.hobby.enigmi
Titolo: Problema matematico

Salve a tutti ho un quesito da proporre:
scrivere in sequenza in ordine crescente i primi 2005 numeri naturali,
cancellare i primi 2, sommarli e posticipare alla sequenza la loro
somma... continuare finchè rimane un solo numero... dire quanto vale
la soma di tutti i numeri scritti...
per chiarezza riporto un esempio con 5 numeri:
1 2 3 4 5
* * 3 4 5 3
* * * * 5 3 7
* * * * * * 7 8
* * * * * * * * 15
la somma di tutti inumeri scritti è 1+2+3+4+5+3+7+8+15=48...
Per piacere, se possibile, riportate anche il vostro ragionamento oltre
al risultato... Grazie, ciao a tutti...

 la somma di tutti i numeri scritti...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
SPOILER?
.
.
.
.
.
.
.
.
.
.
.
.
.
Dunque, il numero da ottenere dovrebbe essere 
2017048048
... non saprei 
spiegare bene come ci sia arrivato (non con la brute force, comunque), ora 
provo a esporlo in un altro post.
-- 
Alessio90 "the Sproloquiator"
"Preferisco essere un uomo di paradossi,
che un uomo di pregiudizi" (Rousseau) 

Scusate per il quote poco ortodosso, ma ho scritto una stupidaggine... non 
fateci caso...


> "LiNuS" ha scritto nel messaggio

Solo una riflessione.
I numeri totali da sommare di tutta la serie saranno 2n - 1 cioè 4009.
Di questi, la somma dei primi 2004 è evidentemente 1002*2005= 2.009.10
La sequenza prosegue con: 2005  3  7  11  15  19  23 ..... 4007
 e poi ancora  2008  18  34  50  66  .... 8002
ecc..
L'ultimo numero dovrebbe essere sui 4 milioni e il totale circa
12 volte la somma dei numeri da 1 a 2004 , cioè poco più di
24 milioni.
Sempre a intuito e se non ho preso una cantonata
Ciao, Nino

 L'ultimo numero dovrebbe essere sui 4 milioni
Sbagliato.
L'ultimo numero è sempre la somma degli n numeri (da 1 a 2005)
cioè è 2.011.015
Nino 


Continuando:
Se il numero finale fosse una potenza del 2, il calcolo è semplice:
Es.: 1 2 3 ....  127 128
 128 = 2^7   n=7
sommatoria da 1 a 128 = (64*129) = 8.256
sommatoria di tutti i tuoi numeri =  8 * 8256 = 66.048
In generale = (n+1) * Nf * (Nf+1)/2
dove: n = potenza del 2
      Nf = numero finale (da 1 a)
Quindi,  da 1 a 2048:
sommatoria = 12 * 2048 * 2049 / 2 = 25.178.112
Ciao, Nino 

Il risultato esatto è 24046868...

 ha scritto nel messaggio
news:1117032659.9...@f14g2000cwb.googlegroups.com...
scusate il risultato  24046868
Esatto... ma la formula?
.
.
.
S
P
O
I
L
E
R
.
.
.
INT(LOG2(N) + 1) * N * (N + 1) / 2 + (2 * (N MOD 2 ^ INT(LOG2(N))) + 1) * (N MOD
2 ^ INT(LOG2(N)))
Dove LOG2 è chiaramente il logaritmo in base 2, INT la parte intera, MOD
l'operatore modulo (resto della divisione).
Per N=2005 si ottiene esattamente il risultato fornito da linus.
Bye
Raf

La formula giusta è

La somma dei primi N numeri interi è
N (N+1)/2
supponiamo infatti di voler sommare i primi dieci numeri interi. In 
questo caso dvremmo sommare insieme
1 2 3 4 5 6 7 8 9 10
l'ordine però lo possiamo scegliere noi, accorgendoci quindi del curioso 
fatto che
1+10=11
2+9=11
3+8=11
4+7=11
5+6=11
Ossia dobbiamo sommare 11 (che è l'ultimo numero più il primo della 
sequenza, ovvero N+1) quante volte? 5 volte, ossia un numero di volte 
pari a N/2.
In effetti alle elementari ci hanno insegnato proprio che sommare tante 
volte lo stesso numero si chiama... moltiplicazione ;-)
Il risultato della somma è dunque
(N+1)*N/2
Si narra che la maestra delle elementari di Gauss, per tenere buona la 
classe chiese ai bambini di sommare i primi cento numeri tra loro (così 
smettevano di rompere le balle e lei poteva tinteggiarsi le unghie, 
anche se questo non viene detto in genere!)
Pare che il piccolo Gauss se ne venne fuori con la soluzione dopo pochi 
secondi, lasciando sbigottita la maestra: come aveva fatto a fare tante 
somme in così poco tempo? In effetti il ragazzino aveva appena scoperto 
il metodo appena esposto.
Il bastardo!
Ah, a proposito:
il sistema funziona anche con le sequenze dispari di numeri: esempino:
1 2 3 4 5
1+5=6
2+4=6
3
In questo caso devo sommare il 6 quante volte? 2 e mezzo!
Che è appunto 5/2, ossia N/2
Resta valido (N+1)*N/2.
P.S.
Giusto per completezza
2005*2006/2=2011015
.Alkemyst.

 .Alkemyst.
Sì, è la formula giusta per ricavare l'ultimo numero della serie, e c'eravamo
già arrivati...
Ma il problema chiedeva di ricavare la somma di tutti i numeri posti in fila,
non solo l'ultimo quindi.
Ad es. per N=5
1 2 3 4 5 3 7 8 15
In questo caso il risultato sarebbe 48.
Per N=2005
1 2 3 4 5 6 7 8 [...] 2005 3 7 11 15 [...] 2011015
La cui somma è 24046868, ottenuta appunto con la formula del mio post
precedente.
Bye
Raf

 anche se questo non viene detto in genere!)
Il maestro si chiamave Büttner, e l'aneddoto e' stato raccontato
in tante varianti che e' difficile sapere quale sia vera.
Vedi:
http://www.maa.org/mathland/mathtrek_10_25_04.html
ciao,
g.

ciao Rafunk, potresti, per piacere tentare di spiegare da dove deriva
la tua formula? Grazie... Ciao... a proposito complimenti....

 la tua formula? Grazie... Ciao... a proposito complimenti....
Grazie. Dunque... non è stato facilissimo, provo a spiegare il mio ragionamento.
F(N) = INT(LOG2(N) + 1) * N * (N + 1) / 2 + (2 * (N MOD 2 ^ INT(LOG2(N))) + 1) *
(N MOD 2 ^ INT(LOG2(N)))
Ho provato a sviluppare le sequenze e a cercare qualche regolarità
N=2: 1 2 3 --> 6
N=3: 1 2 3 3 5 --> 15
N=4: 1 2 3 4 3 7 10 -->30
N=5: 1 2 3 4 5 3 7 8 15 --> 48
N=6: 1 2 3 4 5 6 3 7 11 10 21 --> 73
N=7: 1 2 3 4 5 6 7 3 7 11 10 18 28 --> 105
N=8: 1 2 3 4 5 6 7 8 3 7 11 15 10 26 36 --> 144
In pratica ho notato questo: quando N è una potenza di 2 (N=2^k) l'addendo
N(N+1)/2, che corrisponde all'ultimo elemento della sequenza pari appunto alla
somma dei primi N elementi, compare "decomposto" esattamente k + 1 volte: nei
primi N, poi nei successivi N/2, poi nei successivi N/4 etc. etc.
Esempio N=4 (k=2):
1 + 2 + 3 + 4 + 3 + 7 + 10 = [1+2+3+4] + [(1+2)+(3+4)] + [((1+2)+(3+4))]
Analogamente per N=8, 16 etc...
Quindi per N = 2 ^ k, avremo F(N) = (k + 1) * N * (N + 1) / 2
Ma k=LOG2(N) ==> F(N) = (LOG2(N) + 1) * N * (N + 1) / 2
Quando invece N non è una potenza di 2 (N = 2 ^ k + R), ho notato che, oltre
agli addendi di cui sopra, che compaiono in numero pari all'esponente della
potenza di 2 appena inferiore a N (raggruppati tra quadre), ce ne sono degli
altri "spuri", qui raggruppati tra graffe.
Es.
N=6 ==> k=INT(LOG2(N)) = 2, R=2
La successione è
1, 2, 3, 4, 5, 6, (1+2), (3+4), (5+6), ((1+2)+(3+4)), ((5+6)+((1+2)+(3+4))
La somma della serie è
1 + 2 + 3 + 4 + 5 + 6 + 3 + 7 + 11 + 10 + 21 =
[1+2+3+4+5+6]
+ {(1+2) + (3+4)}    <-- spurio
+ [(5+6) + ((1+2)+(3+4))]
+ [((5+6) + ((1+2)+(3+4)))]
N=7 ==> k=INT(LOG2(N)) = 2, R=3
La successione è
1, 2, 3, 4, 5, 6, 7, (1+2), (3+4), (5+6), (7+(1+2)), ((3+4)+(5+6)),
((7+(1+2))+((3+4)+(5+6)))
La somma della serie è
1 + 2 + 3 + 4 + 5 + 6 + 7 + 3 + 7 + 11 + 10 + 18 + 28  =
[1+2+3+4+5+6+7]
+ {(1+2) + (3+4) + (5+6)}  <-- spurio
+ [(7 + (1+2)) + ((3+4)+(5+6))]
+ [((7 + (1+2)) + ((3+4)+(5+6)))]
Ora: quanto vale la loro somma in generale?
Si può verificare che è pari alla somma dei primi 2R numeri interi, quindi
2R(2R+1)/2 = R(2R+1)
Allora avremo:
F(N) = (k + 1) * N * (N + 1) / 2 + (2 * R + 1) * R
Ma stante N = 2^k + R, e K=INT(LOG2(N)), si ricava R = N MOD 2^INT(LOG2(N)).
Con le debite sostituzioni si ottiene la formula iniziale.
Spero di essere stato esauriente.
Ciao
Raf

 la somma di tutti inumeri scritti è 1+2+3+4+5+3+7+8+15=48...
Premesso che si tratta di uno dei giochi della finale nazionale dei 
campionati internazionali di giochi matematici (citare la fonte non fa mai 
male!) organizzati in Italia dalla Bocconi 
(
http://matematica.uni-bocconi.it
), sono venuto a conoscenza di una 
soluzione particolarmente elegante (purtroppo non mia).
Come qualcuno ha già osservato il problema sarebbe piuttosto semplice se 
fossimo in presenza di una potenza di due... allora facciamola saltare 
fuori! Ovvero immaginiamo di fare le somme fino a quando avremo esattamente 
tanti numeri quanti una potenza di due, nel nostro caso 1024.
Da quel punto in poi tutte le iterazioni successive daranno la stessa somma, 
ovvero avremmo 11 volte la somma di questi numeri, a cui dovremo sommare 
tutti i numeri precedenti all'arrivo ai 1024.
Per arrivare a 1024 numeri, partendo da 2005, ne dovremo togliere 981, 
ovvero dovremo fare le prime 981 somme cioè togliere i primi 1962 numeri e 
scrivere le varie somme.
Riepilogando troviamo la somma dei primi 1962 numeri, poi ci sommiamo 11 
volte la somma dei primi 2005 numeri ed il gioco è fatto
TOT = (SOMMA DA 1 A 1962) + 11 * (SOMMA DA 1 A 2005) =
    = (1962 * 1963) / 2 + 11 * (2005 * 2006) / 2 =
    = 1925703 + 22121165 =
    = 24046868
-- 
[fadeout]