OliForum Matematico

MindFlyer ha spostato questo scempio di thread.
------------------------------------------------

eccovi l'infame quesito che ieri m'ha tormentato ai giochi bocconi.
anche adesso la soluzione non mi è chiara per niente, quindi lo do volentieri in pasto agli squali del sito, buon divertimento.

scritti in fila gli interi da 1 a 2005, cancellate i primi due e scrivete in fondo la loro somma. reiterate il procedimento finchè non rimane un solo numero.
qual'è la somma di tutti i numeri scritti (compresi i primi 2005)?

Per ogni $ k\in\mathbb{N} $, sia $ \displaystyle s_k := \sum_{i=0}^{2k} i = k(2k+1) $. E allora, posto $ \displaystyle S := \sum_{i=1}^{2005} i = 2005\cdot 1003 $, il quesito chiede d'esprimere in forma chiusa la somma $ \displaystyle \sigma := \sum_{k=0}^{1002} (S - s_k) = 1003\cdot S - $ $ \displaystyle\sum_{k=1}^{1002} k(2k+1) = 1003\cdot S - 2\cdot \sum_{k=1}^{1002} k^2 - 501\cdot 1003 $. E siccome, per ogni $ n\in\mathbb{N} $: $ \displaystyle\sum_{i=0}^{n} i^2 = \dfrac{n(n+1)(2n+1)}{6} $, fatti due conti si trova (modulo errori inattesi e con un po' di pazienza... ): $ \sigma = 1003^2\cdot 2005 - 334 \cdot 1003 \cdot 2005 - 501\cdot 1003 = $ $ 1003 \cdot (669 \cdot 2005 - 501) = 1344866532 $.

ora, la domanda è: "cosa si fuma euler?"
dunque, osservazione: la somma totale dei numeri resta costante, perché tu togli due numeri e aggiungi la somma.
l'ultimo numero rimasto sarà la somma di tutti i numeri scritti all'inizio.
ora, gauss docet: $ 1+2+\cdots+2005 = {2006\cdot2005\over2} = 2011015 \mod erroridicalcolo $.

e no ma_go... l'esercizio chiede la somma di TUTTI i numeri SCRITTI. Non dei numeri iniziali.

ups...
beh, va beh...
da qui il gioco è fatto: ad ogni passo viene rimosso un numero (complessivamente), quindi ci vorranno 2004 passaggi... quindi $ 2011015\cdot2004 = boh $.
sbaglio?

edit: no, ok, ho frainteso mi ritiro in silenzio stampa... sorry per le cazzate

ma_go ha scritto:ora, la domanda è: "cosa si fuma euler?"

E a questa ci aggiungerei pure: "Quand'è che il nostro ma_go si risolverà di cambiare pusher?" Davvero circola roba pesante, laggiù nel borgo di Pisa, se il tuo radioso nume Matematico si rivela così confuso nei pur tenui vapori dell'ora meridiana... Che Dio possa aver pietà della tua anima, mio caro, perch'io non intendo averne della tua impudenza!

jabberwocky ha scritto:[...] Scritti in fila gli interi da 1 a 2005, cancellate i primi due e scrivete in fondo la loro somma. [...]

Qualcuno mi fa notare che ho probabilmente frainteso completamente la traccia del problema!!!

Uhmmm... Dunque si scrive in fondo la somma degli interi cancellati ad ogni nuova iterazione? No, lo chiedo perch'io avevo inteso tutt'altra roba (e mi rendo conto che forse ho sbagliato di brutto!!!):

somma <---- 1 + 2 + 3 + 4 + 5 + 6 + ... + 2005
+ somma <-- 3 + 4 + 5 + 6 + ... + 2005
+ somma <-- 5 + 6 + ... + 2005
... ... ... ... ...
+ somma <-- 2005
-------------------------------------------------------
= Totale

Me lo sono inventato, vero?!? Sono un tipo fantasioso, però, suvvia...

Si tratta dunque di sommare tutti i numeri cancellati ad ogni iterazione, e aggiungere al parziale ottenuto la somma di tutti gli interi da 1 a 2005, per avere quindi $ (1+2) + (2+3) + \ldots + (2003 + 2004) + $ $ (1 + 2 + \ldots + 2005) = 2005^2 $ ?!?

Io proverei a dividere il tutto in "passate". Chiamo S la sommatoria dei primi 2005 numeri...

1a passata:

ottengo 1003 numeri:

2005-3-7-11-15-19-23-27...3999-4003-4007

ho scritto (S-2005)

2a passata:

ottengo 502 numeri:

4007-2008-18-34-50-66-...-7970-7986 - 8002

ho scritto (S-4007)

3a passata

ottengo 251 numeri:

6015-52-116...- 15988

ho scritto (S)

4a passata

ottengo 126 numeri

15988-6067-372-500-...- 31976

ho scritto (S-15988)

5a passata

ottengo 63 numeri

ho scritto (S)

e così via (ora nn faccio i calcoli dato che cmq li sbaglierei)... si nota cmq che le serie di numeri scritti contengono serie aritmetiche di ragione 4,16,64,256,1024,4096... (per semplificare i calcoli)

alternativamente ad ogni passata o si somma S se i numeri rimasti sono pari oppure si somma S-tot se sono dispari... da notare che la 6a passata è l'ultima che pone problemi, dato che dopo si ottiene 32, che è una potenza di 2...

Se è esatto il proc, pare il solito es Bocconi ultracalcoloso... (tipo quello appena postato da Biagio in combinatoria)...

Possibile che abbia frainteso completamente il problema, ma per come l'ho capito io il risultato dovrebbe essere 2011015, ossia la somma dei primi 2005 numeri, dato che alla fin fine lo spostare in fondo la somma di due numeri al posto di questi ultimi e ripetere il procedimento è solamente un modo per commutare e associare diversamente gli addendi. Godendo la somma in $ \mathbb{N} $ della proprietà associativa e commutativa...
Ma si sa almeno quanto dovrebbe essere il risultato?

Ma se è teoria dei numeri questa...
Via, spostiamo!

Quello postato da carro_bestiame è parente di questo... spostare pure quello?

Allora, eccovi la formula generale!

Se al posto di 2005 mettiamo n, e poniamo $ k=\lfloor\log_2 n\rfloor $, allora la somma di tutti i numeri scritti è

$ \displaystyle \frac{n(n+1)(k+1)}{2}+(n-2^k)(2n-2^{k+1}+1) $.

In particolare, ponendo n=2005 si ottiene 24046868.

argh... non avevo capito un .....

Ehmmm... C'è qualcuno disposto a spiegarmi con diffuse parole in che modo debbo interpretare il testo del problema, cosicché anch'io possa capire da dove salta fuori la soluzione di MindFlyer?!? Grazie...