Newsgroup: it.economia.borsa
Titolo: [OT] Npn rompete le palle

Sei stato incaricato di testare la resistenza alla rottura di una partita
di palle da biliardo.
Il tuo capo ti ha dato solo due palle per il test, che consiste nel
lancio della palla da uno dei 105 piani di un grattacielo, e verificare
fino a quale piano può cadere senza rompersi.
Ovviamente, se inizi dal primo piano e sali un piano per volta te la
caveresti anche con una sola palla. Ma il problema ti chiede di
trovare la strategia che minimizza il massimo numero di lanci
necessari nel peggiore dei casi.
Nota: se ti si rompe anche la seconda palla prima di aver trovato
il carico limite, non puoi portare a termine il lavoro e sei licenziato.
Come procederesti e qual è il numero minimo di lanci nel peggiore
dei casi?
Buona notte!
Nino 

 casi?
52
..

52
Una soluzione ovvia dà 53, e non ne vedo di migliori.  Come hai fatto a
fare 52?

fare 52?
Ho trovato una strategia migliore.  Riesco a farlo con 36 tiri.  Si può
far di meglio?

 far di meglio?
Anche a me da 52... 36 non riesco proprop a vederlo.

 ha scritto nel messaggio 
news:873ao23...@tucano.isti.cnr.it...

Certamente, sì.
E di molto :-) 

 ..
Si puň fare molto meglio... 

Francesco Potorti` ha scritto:

A occhio direi 19.
Ciao ... Dino

 Anche a me da 52... 36 non riesco proprop a vederlo.
Anche 36 è troppo...
Si può migliorare di molto... 

"ginopilotino" <gi...@pilotino.invalid> ha scritto nel messaggio 
news:483d1290$0$35953$4faf...@reader2.news.tin.it...

A occhio direi 19.
Ciao ... Dino
-----> Hai un buon occhio, ma non ci siamo ancora... 

Nino ha scritto:

Oh, perbacco, pensavo fosse un int(105/n+n-1).
Hai rotto con sti giochetti, non mi lasci lavorare :D
Ciao ... Dino

ginopilotino ha scritto:

Ah no, bastano solo 14 lanci :)
Ciao ... Dino

"ginopilotino" <gi...@pilotino.invalid> ha scritto nel messaggio 
news:483d1410$0$35953$4faf...@reader2.news.tin.it...


Ciao ... Dino
----> Non sarebbe migliore la vita, se lavorare significasse
risolvere questi giochetti? 

"ginopilotino" <gi...@pilotino.invalid> ha scritto nel messaggio 
news:483d14f7$0$35953$4faf...@reader2.news.tin.it...


Ciao ... Dino
----> E bravo, il nostro Dino... Anche questo l'hai risolto. :-)
Aspetta qualche ora per la spiegazione, magari qualcun altro
vorrebbe arrivarci da solo. 

Nino ha scritto:

"Come procederesti e qual è il numero minimo di lanci nel peggiore
dei casi?"
Mi confermi PEGGIORE DEI CASI ?

 ha scritto nel messaggio 
news:oQ8%j.86824$FR.3...@twister1.libero.it...

Sì.
Qualunque sia il piano del grattacielo da cui la palla  si rompe.
L'analisi vale se si esaminano i piani dal primo all'ultimo.... 

 
Vabbè, devo uscire, mi arrovellerò in moto, confidando di trovare la
soluzione al mio ritorno ;-)

 ha scritto nel messaggio 
news:i%8%j.86831$FR.3...@twister1.libero.it...

Vai piano, e non distrarti... :-) 

 L'analisi vale se si esaminano i piani dal primo all'ultimo.... 
Secondo me questa cosa trae un poco in inganno.
Cmq per arrivare a 19 e' facilissimo, poi bisogna un po' ragionarci su, 
"distribuire" in qualche modo ;)
Ciao ... Dino

 vorrebbe arrivarci da solo. 
Secondo me a nessuno gliene frega un bip :D
Cmq la soluzione piu' intuitiva e' quella di usare un passo costante per 
la prima palla, fino a quando si rompe, poi con la seconda provare 
partendo dal piano subito sopra quello a cui la prima non si e' rotta.
In questo modo, con un passo 10, si ottiene, nel caso peggiore, appunto 
10 piu' 9, dove questi ultimi sono i tentativi massimi da fare tra il 
piano dove la palla si e' rotta e quella dove non si e' rotta.
Cosi' facendo pero' il caso peggiore e' solo quello in cui la palla si 
rompe al 100esimo piano e dobbiamo riprovare dal 91 in su, quindi al 
massimo 10+9.
Ma se la palla si rompesse al decimo, cioe' subito, sarebbero solo 10 
tentativi massimi per trovare il limite, cioe' 1+9.
E cosi' non va bene. :)
Ciao ... Dino

 Cmq la soluzione piu' intuitiva
Sě, ma avevo chiesto:
"la strategia che minimizza il massimo numero di lanci
necessari nel peggiore dei casi."
Che in problemi di questo genere č la soluzione piů brillante.

 Che in problemi di questo genere è la soluzione più brillante.
Stavo solo cercando di dare un aiutino :)
Non dico di piu' altrimenti diventa troppo facile.
Ciao ... Dino

Secondo me a nessuno gliene frega un bip :D
No, invece io l'avevo risolto, ma quando sono andato a scriverlo ero
stato anticipato da te :)

dei casi?
procederei con una ricerca dicotomica! ;)
-----------------------------------
Inviato tramite il servizio gratuito 
http://www.tubemessage.com

 ha scritto nel messaggio 
news:87ve0y1...@tucano.isti.cnr.it...

Al prossimo, allora... ;-) 


Non penso sia così complesso :) 


A chi interessa, e non dovesse aver trovato la soluzione:
S
.
P
.
O
.
I
.
L
.
E
.
R
....
....
....
....
Lancio la prima palla dai seguenti piani:
14°
27°
39°
50°
60°
69°
77°
84°
90°
95°
99°
102°
104°
105°
Se, e appena si rompe, testo uno per uno i piani che seguono
il tentativo precedente.
Il massimo (rottura esattamente a uno dei piani indicati sopra
o a quello immediatamente precedente) comporta 14 lanci.
Nino

procederei con una ricerca dicotomica! ;)
La ricerca dicotomica richiede 53 tentativi, perché si può dividere per
2 una sola volta...

Nino ha scritto:

Per i piu' smaliziati, si tratta semplicemente, dato n l'ampiezza del 
primo intervallo di piani, di trovare la soluzione a n+(n-1)+(n-2) ... 
+(n-n+1)=105
Questo perche' con il primo intervallo pari a n, occorrerra' fare in 
tutto 1+(n-1) cioe' n tentativi, nel caso peggiore, cioe' ammettendo che 
la prima palla si rompa subito e la seconda palla si rompa all'ultimo 
tentativo, cioe' dopo aver tentato dal piano 1 al piano n-1. Per il 
secondo intervallo, qualora la palla non si sia gia' rotta, invece siamo 
gia' al secondo tentativi, quindi riduciamo l'intervallo di 1 e abbiamo 
2+(n-2), cioe' sempre n nel caso peggiore. E cosi' via.
Cioe' ogni volta che si passa al tentativo successivo con la prima 
palla, si diminuisce di 1 l'intervallo di piani, perche', appunto, si 
sta facendo una prova in piu'. Questo per "distribuire" il caso piu' 
sfavorevole su tutti gli intervalli di lancio della prima palla.
Quindi sommiamo questi intervalli che ottimizzano l'esperimento e 
risolviamo l'equazione: Sommatoria per i che va da 0 a n-1 di (n-i) = 
105. Il valore di n sara' ovviamente compreso tra 10 e 19, quindi la si 
puo' anche risolvere per tentativi. :)
Ciao ... Dino

 puo' anche risolvere per tentativi. :)
Ovviamente scherzavo eh! Non e' che qualcuno davvero e' andato a 
sostituire per tentativi da 10 a 19 ed ogni volta a rifarsi le somme :D
Per risolvere l'equazione basta sommare 1+2+3+4+ ecc ecc fino a quando 
la somma non da 105. L'ultimo numero aggiunto e' la soluzione del problema.
Ciao ... Dino

"ginopilotino" <gi...@pilotino.invalid> ha scritto nel messaggio 
news:483d8db9$0$40210$4faf...@reader5.news.tin.it...

Allora, diciamola tutta...
Da : "n+(n-1)+(n-2) ... +(n-n+1)=105"
la soluzione non è nient'altro che la somma dei numeri interi da 1 a n, che,
come già Gauss sapeva a 8 anni, è uguale a       n*(n+1)/2
Quindi   n(n+1) = 210
n^2 + n - 210 = 0
Equazione di secondo grado che dà come soluzioni +14 (accettabile) e
-15 (ovviamente da scartare).


dici che la palla si rompe alla prima divisione?


 dici che la palla si rompe alla prima divisione?
No, si rompono tutte e due :D
Ciao ... Dino

dici che la palla si rompe alla prima divisione?
Nel caso peggiore, sì.

 ha scritto nel messaggio 
news:483d95c9$0$18148$4faf...@reader3.news.tin.it...

Il mio jr non ha capito la formula.....e neanche io sono riuscito a 
spiegargliela..(sono a corto di funzioni gaussiane....colpa dei PC!!!)  :-(
Se n = 105  ......perchè n(n+1) = 210?
Aggiungendo: "Se n = 14 a cosa serve fare tutti quei calcoli complessi, 
essendo la risposta corretta?", "E soprattutto....come trovo 14?"
Aiutami con una risposta semplice...  ;-) 

essendo la risposta corretta?", "E soprattutto....come trovo 14?"
Io ci sono arrivato così, ma probabilmente se si ragiona a ritroso
(partendo da un grattacielo con pochi piani) si fa anche prima.
Il primo tiro lo fai da un piano basso n, per escludere i primi n piani.
Se si rompe, hai bisogno di n tiri (uno che si rompe più n+1 con l'altra
palla).  Se non si rompe, ti ritrovi nella stessa situazione di prima,
ma con 105-n piani da verificare invece di n, e un tiro già fatto.
Quindi, ragionando come prima, fai il tiro successivo per escludere i
successivi n-1 piani (quindi tiri dal piano 2n-1).  Se non si rompe ti
sposti in alto per escludere i successivi n-2 piani e così via.  Hai una
sequenza di somme di numeri descrescenti, il resto dovrebbe essere
facile.  Viene 14 perché somma(i,1,14)(i)=105.

 facile.  Viene 14 perché somma(i,1,14)(i)=105.
Il jr mi chiederà: "se sommo 1n + 2n-1 + 3n-2 + 4n-3 + .... fino a 
105.....troverò sempre 105!"
Help ;-)
P.S. Il jr ha 12 anni...... 

Francesco Potorti` ha scritto:

Esatto. Pensavo di averlo spiegato chiaramente anche io :(
Ciao ... Dino

 Aiutami con una risposta semplice...  ;-) 
Se non hai capito con l'intervento di francesco portorti' fammi sapere, 
mi affascina riuscire a trovare un modo il piu' chiaro possibile per 
spiegare le cose.
Ciao ... Dino


Lascia perdere la formula... e torniamo al problema.
(per te: non è n=105, ma la somma di n+(n-1)+(n-2)+...1 = 105
La somma dei numeri naturali da 1 a 10 è = 10x11/2 = 55, cioè n*(n+1)/2
Qui si ha    n*(n+1)/2 = 105   da cui  n*(n+1) = 105*2 = 210  )
Devi trovare il piano oltre il quale la palla si rompe, ma rendendo minimi
i lanci della palla stessa.
Se non ci fosse il fatto che hai a disposizione solo due palle, il metodo
migliore (che ti dà il risultato con meno tentativi) è quello binario, cioè 
di
partire da metà grattacielo (es. al piano 52); se si rompe vai a metà, cioè 
al
26, se no sali al 78; poi al 13 o 39 (o al 65 o 91), ecc.. e in breve arrivi 
al
risultato (7 tentativi max, perchè 105 è minore di 2^7).
Ma qui hai la limitazione di poter sbagliare solo una volta in eccesso, 
perchè
disponi solo di due palle; dopo che si è rotta la prima, puoi solo provare 
con
la seconda un piano per volta (a salire).
Il sistema più intuitivo è dividere i piani del grattacielo es. per 10 e 
cominciare
a buttare la prima palla dal decimo piano; se si rompe, con la seconda 
scendi
al primo piano e prosegui verso l'alto: in 10 tentativi, fino al nono piano, 
risolvi
senz'altro il problema. Se invece al 10 piano non si rompe, sali al 20 piano 
e da
lì ripeti la procedura (lanci, vedi se si rompe, ecc..). Se non si rompe, 
sali al
30 piano, ecc...
In questo modo, se hai la sfortuna che la palla resiste oltre il 90 piano, 
in questo
modo i tentativi possono essere fino ad un massimo di 19.
Quindi, questa strategia non è equilibrata, perchè il risultato cambia (da 
10 a 19):
per ottimizzarla occorre variare gli intervalli, cioè il numero dei piani 
inizialmente
deve essere maggiore e mano a mano diminuire.
Questo si realizza scegliendo per i primi lanci i seguenti piani:
14; (14+13); (14+13+12); (14+13+12+11); ..... conformemente alla soluzione
che ho indicato nel post delle 16:29.
Spero di aver chiarito
Nino 

 105.....troverò sempre 105!"
Esatto, ma l'ultimo numero che sommi e' la soluzione.
Ciao ... Dino

 piano?"
Nessuno!
Ma potrebbe rompersi anche al centesimo piano.
E, in questo caso, se parti dal primo, poi sali al secondo, poi al terzo, 
ecc.
i tentativi diventano ben 100; e il problema vuole la soluzione minore in
qualsiasi caso, cioè qualsiasi sia il piano oltre il quale la palla si 
rompe.
Pe questo, devi partire da un certo piano (es. decimo), anche se la palla
si dovesse rompere al primo (faresti un tentativo in più, 2 invece di 1,
ma in tutti gli altri casi, cioè che non si rompe al primo, avresti un 
vantaggio)