bocconi 2005, una somma da 24 milioni

Giochini matematici elementari ma non olimpici.
jabberwocky
Messaggi: 163
Iscritto il: 01 gen 1970, 01:00

bocconi 2005, una somma da 24 milioni

Messaggio da jabberwocky » 15 mag 2005, 10:54

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)?

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 15 mag 2005, 11:18

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... :roll:): $ \sigma = 1003^2\cdot 2005 - 334 \cdot 1003 \cdot 2005 - 501\cdot 1003 = $ $ 1003 \cdot (669 \cdot 2005 - 501) = 1344866532 $.
Ultima modifica di HiTLeuLeR il 15 mag 2005, 11:43, modificato 1 volta in totale.

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 15 mag 2005, 11:38

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 $.

AleX_ZeTa
Messaggi: 625
Iscritto il: 01 gen 1970, 01:00
Località: Milano
Contatta:

Messaggio da AleX_ZeTa » 15 mag 2005, 11:43

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

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Messaggio da ma_go » 15 mag 2005, 11:53

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 :P

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 15 mag 2005, 12:11

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! 8)

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 15 mag 2005, 14:45

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... :roll:

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 15 mag 2005, 15:00

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 $ ?!?

Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info » 15 mag 2005, 16:42

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

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 15 mag 2005, 17:16

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?
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

MindFlyer

Messaggio da MindFlyer » 15 mag 2005, 18:06

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

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 15 mag 2005, 18:08

Quello postato da carro_bestiame è parente di questo... spostare pure quello?
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

MindFlyer

Messaggio da MindFlyer » 15 mag 2005, 18:42

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.

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 15 mag 2005, 18:49

argh... non avevo capito un ..... :D
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 15 mag 2005, 20:00

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... :?

Rispondi