Newsgroup: it.hobby.enigmi
Titolo: cadere, o o...

abbiamo un grattacielo di 100 piani e 2 sfere di cristallo.
dobbiamo determinare il piano più basso dal quale le sfere si rompono, nel
minor numero di tentativi.
abbiamo la possibilità di recuperare le sfere solo se non si rompono.
che metodo usiamo?

 wrote in message
news:jKiU8.97457$j65.2...@twister1.libero.it...

A occhio:
Parto dal piano terreno e salgo di due piani alla volta. Ogni volta lascio
cadere la sfera. Se non si rompe continuo, se si rompe provo con la sfera
che mi rimane se al piano immediatamente sotto  a quello dove mi si è rotta
la prima si rompe anche la seconda.
Ciao
Pietro



.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
sara' sicuramente migliorabile comunque:
lancio la prima sfera dai piani 10 20 30 40 ... finche' non si rompe
supponiamo al piano x. A questo punto lancio la seconda sfera dai
piani x-9, x-8, x-7 .... finche' non si rompe anche questa.
nut
a questo punto lancio la seconda 
--------------------------------------------------
stat nutella pristina nomine, brufola nuda tenemus

 ha scritto nel
messaggio news:jKiU8.97457$j65.2...@twister1.libero.it...

.
.
.
.
.
.
.
.
.
.
A me risulta che nel caso peggiore ho bisogno di 19 tentativi, che si può
ottenere in diversi modi ma tutti con la stessa logica...
Il mio metodo è questo:
prendo la prima sfera e la butto dal primo piano, poi dal secondo e cosi'
via finche' si rompe: il caso peggiore mi da' 100 lanci (!) però salvo
sicuramente una sfera;
prendo la prima sfera e la butto dal 2 piano, poi dal 4 poi dal sesto, ecc.
finchè si rompe e uso la seconda per determinare se il piano dispari
immediatamente precedente salva la sfera o la rompe (qui ho il 50% di
probabilita' di salvare la sfera...): max 50 lanci;
prendo la prima sfera e la butto da 3, 6, 9, ecc. e uso la seconda per
determinare il piano con certezza (es. la prima si rompe al 9: butto la
seconda adl 7, poi dall'8 e determino quale piano):max 33+2 lanci.
Proseguendo con lo stesso meccanismo trovo che con "intervalli" di 8, 9 10,
11, 12 e 13 piani nel caso peggiore ho bisogno di 19 lanci.
Forse ho sbagliato i conti, ma mi sembra che il ragionamento funzioni (dopo
l'"intervallo" di 14 piani il numero di lanci necessario torna a crescere)
--
Jenga ^_^
"Hai la capacita' di imparare dai tuoi errori. Oggi imparerai un sacco."

 wrote in message
jKiU8.97457$j65.2...@twister1.libero.it...

Spoiler
Spoiler
spoiler
Si potrebbe partire dal terzo piano lanciando una delle 2 sfere se si rompe,
lanciamo l'altra dal secondo e se anche questa si rompe sapremmo che il
piano più basso è il primo altrimenti sarà il secondo; se invece la prima
sfera non si rompe la lanceremo dal sesto ripetendo gli stessi procedimenti
cioè:
se si rompe lanciamo l'altra dal quinto
se non si rompe lanciamo di nuovo la prima dal nono
E così via procedendo di 3 piani alla volta fin quando non individuiamo il
piano più basso.
In questo modo occorreranno 33 tentativi.
Non escludo che si possa fare anche in meno però per ora non mi viene in
mente di meglio
Ciao
IL Polle

dimenticavo: in tutto si vengono cosi' a dover fare nel caso peggiore
18 tentativi


stefano pascolutti wrote:

E' un problema molto bello !
Peccato che lo abbiamo gia' trattato in passato, a me piaque molto.
Invito chi non lo conosce a pensarci un po' su...

l'"intervallo" di 14 piani il numero di lanci necessario torna a crescere)
se chiamiamo n il numero di piani per ogni intervallo (ossia, n=1 vuol
dire lanciarla da *ogni* piano, n=2 vuol dire uno si' e uno no, n=3
vuol dire uno si' e due no, e cosi' via...), il numero totale di lanci
necessario nel caso peggiore e' sempre 
nl  = 100/n + n - 1
dove il primo termine si approssima alla sua parte intera.
Generalizzando la funzione nl (n) a tutti i numeri, anche non interi,
si trova che ha un minimo effettivo per n = 10, che guarda caso e'
pure intero e ci va benissimo (e in quel caso il numero totale di
lanci "massimi" e' appunto esattamente 19)  Per n = 8, 9, 11, 12 e 13,
il valore della funzione generalizzata non e' piu' sul minimo, e il
suo valore *non* e' intero, ma ha sempre una parte intera uguale a 19.
Non mi e' ben chiaro se questo significa qualcosa per l'effettivo
aumento della probabilita' di aver bisogno di qualche lancio in piu',
ma mi pare di no. In fondo, la funzione nl(x) = 100/x + x -1, con x
numero reale, ha un solo minimo per x = 10, ma forse la successione
nl(n) = int(100/n) - n +1, con n intero, ha tutto un plateau di
minimi, che vanno da 8 a 13...
ciao
Lisa

  Mi e' caduta la "c" dal sesto piano!

 ha scritto nel messaggio
news:3d21d273...@diesel.cu.mi.it...


 lanci "massimi" e' appunto esattamente 19)  
Proviamo a fare di meglio:
Se voglio fare meno di 19 lanci (supponiamo che voglia provare con 15), 
potrei ragionare cosi`:
Provo al piano 15: se la sfera si rompe (sfortuna!) mi tocca di fare tutti 
i 14 tentativi con l'altra: 14+1=15.
Se mi e` andata bene devo risolvere un problema piu` semplice: solo 85 
piani con 14 tentativi rimasti e due sfere!
Quindi provero` ai piani 15+41, 15+14+13, 15+14+13+12, ...
A questo punto la successione e` decisa, devo solo dire qual e` il primo 
piano da cui provo (magari con 15 ce la faccio, ma magari no o magari si 
puo` fare di meglio).
A me pare che si debba trovare il piu` piccolo numero triangolare piu` 
grande di 100, che dovrebbe essere 105, corrispondente al piano 14.
Dovremmo quindi farcela con 14 lanci.
Ciao,
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli/

 Quindi provero` ai piani 15+41, 15+14+13, 15+14+13+12, ...
Supponi che la prima sfera si rompa al piano 15+41: con l'altra (unica sfera
integra) devi per forza partire dal piano 16 e salire uno alla volta, se
vuoi la *certezza* di trovare il piano da cui si rompe... quindi il caso
*peggiore* sarebbe 15+40...
O magari ho capito male la sequenza dei lanci successivi al primo?


 quindi il caso *peggiore* sarebbe 15+40...
No, in questo caso so gia` che fino al 15 non si rompe, quindi dovrei fare 
1+40 lanci. Comunque l'idea era di farne 14 e non 40 ...


 ha scritto nel
messaggio news:jKiU8.97457$j65.2...@twister1.libero.it...

in 14 lanci:
lancio la prima sfera fino alla rottura a questi piani:
14-27-39-50-60-69-77-84-90-95-98
(salto 14-13-12.. ecc. piani)
alla rottura della prima sfera,
a = piano a cui la prima sfera si è rotta (esempio 50)
b = lancio precedente (esempio 39)
comincio a lanciare la seconda  da (a+1) fino a (b-1)
In questo modo nel caso peggiore ho al massimo 14 lanci.

 1+40 lanci. Comunque l'idea era di farne 14 e non 40 ...
OK! questo invece era un errore di sbaglio...(per la serie: "in questa nuova
edizione del libro sono stati corretti molti dei precedenti errori di
stUmpa")


 (salto 14-13-12.. ecc. piani)
Propongo di generalizzare avendo a disposizione 3 sfere al posto di 2.
Alla luce della soluzione precedente e' abbastanza facile.
ciao a tutti

 wrote in message
jKiU8.97457$j65.2...@twister1.libero.it...

r
i
c
e
r
c
a
d
i
c
o
t
o
m
i
c
a
?
dovrebbero bastare 7 tentativi
ciao
carlito

 wrote in
news:afvprn$t4$
1...@newsreader1.mclink.it
: 

Con la ricerca dicotomica proveresti al 50esimo piano:
    	*crash*
si e` rotta la prima sfera! Segno che e` ad un piano inferiore: proviamo 
al 25esimo
    	*crash*
si e` rotta anche la seconda!
E adesso?
Ciao,
Marco


Si potrebbe fare un lancio con la prima sfera ai piani:
36 64 85 100
con la seconda se la prima si rompe al piano:
rottura al  lanci 2ª sfera
  36:         8 15 21 26 30 33 35
  64:        43 49 54 58 61 63
  85:        70 75 79 82 84
100:        90 94 97 99
e usare la terza per individuare il piano esatto.
In totale sono 9 lanci.
bye
fraka

 Propongo di generalizzare avendo a disposizione 3 sfere al posto di 2.
Matematici alla riscossa :)
Noto con estrema soddisfazione che l'area logico-matemetica si è risvegliata
alla grande (ben arrivato a quick nick e a agli altri nuovi entrati), anche
se non posso dedicarvi il tempo che vorrei :(
veniamo al problema. Come fai notare tu, la generalizzazione è semplice:
- Con una sfera non possiamo far altro che tentare tuttti i piani dal basso.
- Con due sfere dobbiamo fare in modo che, se la prima sfera si rompe dopo k
tentativi, restino da testare un numero di piani n-k in modo da non superare
gli n tentativi totali. Quindi il primo tentativo va effettuato al piano n,
il secondo dopo altri n-1 piani e così via. Si tratta in pratica di trovare
il più piccolo triangolare che supera 100.
- Con tre sfere il discorso è lo stesso, solo che gli intervalli li
scegliamo in modo da massimizzare i piani che possiamo testare con due
sfere, quindi saranno tutti numeri triangolari decrescenti. Allora si tratta
di trovare il più piccolo n tale che (1+T1)+(1+T2)+..(1+Tn)>100. Questo
succede per n=8 e basterebbe fino a 120 piani. I piani da segliere sono
T8+1       = 37
T8+T7+2    = 66
T8+T7+T6+3 = 88
T8+..+T5+4 = 104
T8+..+T4+5 = 115
T8+..+T3+6 = 122
T8+..+T2+7 = 126
T8+..+T1+8 = 128
Ovviamente se sono solo 100 piani non prendiamo di certo un elicottero ;)
Generalizzare per n sfere diventa facile, basta prendere la sequenza trovata
per n-1 sfere e costruire la serie delle somme parziali, aggiungendo 1 ad
ogni termine.
--
Ciao, Silv:o)

 14-27-39-50-60-69-77-84-90-95-98
Mi chiedevo: se invece di minimizzare il massimo numero di lanci,
cercassimo di rendere minimo il numero medio di lanci, quale sarebbe la
soluzione ottimale? 
Se non ho sbagliato i calcoli, la strategia di nick porta ad una media
di 11,34 lanci, mentre la strategia "di dieci in dieci" ottiene una
media di 11,9. Si puň fare meglio?
Maurizio

 ogni termine.
Ok, ma matematicamente parlando, se ho N sfere qual'č la formula che mi dice
a che piano devo cominciare ?
cioč, se ho due sfere so che la formula č data (piu' o meno;-) da:
piano iniziale = (SQRT(1+8N)-1)/2
se non erro ricavata da:
N = SOMMATORIA per x da 1 a K di x = k*(k+1)/2
quindi se ho tre sfere la formula diventa:
N = SOMMATORIA per x da 1 a K di x*(x+1)/2 = ?
che, e qua mi fermo dato che di matematica mi ricordo poco, tradotto in una
formula potrei poi ricavarmi x dato N.
Detto questo, chiedo (non so la risposta), č possibile trovare una formula
che date K sfere e N piani mi dica a che piano cominciare ?
ovviamente con 2^K < N, perchč in tal caso uso una ricerca dicotomica e il
gioco č fatto.