100 piani
100 piani
Avete 2 palle di vetro uguali, avete un palazzo di 100 piani, dovete individuare il piano più alto dal quale facendo cadere la palla di vetro, non si rompe. Se dopo un tentativo (di lancio di 1 palla da un piano qualsiasi)1 palla si rompe allora non è più utilizzabile. Qual è il numero minimo di tentativi (naturalmente nel caso più sfortunato) che bisogna fare per trovare tale piano?
Appassionatamente BTA 197!
Chiamiamo le due palle A e B, p il piano in cui siamo, P il piano da trovare. Poichè A e B sono identiche, arriva prima al suolo quella lanciata da un'altezza maggiore. Posizioniamoci in p=1 e lanciamo la palla B in modo che raggiunga p+1=2. Prima che ricadendo ci passi davanti lasciamo cadere la palla A. Poichè B cade da un'altezza maggiore di A, si possono verificare tre casi: (1) A e B rimangono intatte, quindi P>p+1=2 (2) si rompe solo B, quindi P=p+1=2 (3) si rompono prima A e poi B, quindi P=p=1. Ripetiamo questa procedura salendo di due piani (p = p+2) finchè non si verificano i casi (2) o (3). Nel caso peggiore, cioè quando P=100, bisogna fare 50 lanci di A e B. Questo è il numero minimo, infatti per lanci di B distanti più di un piano dai lanci di A o per incrementi di piano maggiori di due non è possibile, osservando l'esito dei lanci, determinare univocamente P.
Nessun uomo è un'isola (J. Donne)
Noticina personale: questo problema l'avevo già visto ma non ero riuscito a risolverlo né a capirne bene la soluzione, se non l'idea di base. Adesso non me la ricordo più ma come ogni tanto mi succede sono riuscito a ricordarmi l'idea risolutiva e da lì a trovare una soluzione (credo) completa del problema, grazie anche a Grapher.
La risposta dovrebbe essere 19 ma non ho decisamente il tempo per postare la mia soluzione... forse domani (spero)
Giusto un hintino: Se procediamo partendo da terra e salendo di un piano alla volta buttando ogni volta la palla a terra siamo sicuri di farcela... ma ci vogliono 100 tentativi e non sfruttiamo la seconda palla. Forse dovremmo dividere i compiti (e il palazzo) tra le due sfere di cristallo in intervalli... basta, ho già detto troppo.
A presto
Ob
La risposta dovrebbe essere 19 ma non ho decisamente il tempo per postare la mia soluzione... forse domani (spero)
Giusto un hintino: Se procediamo partendo da terra e salendo di un piano alla volta buttando ogni volta la palla a terra siamo sicuri di farcela... ma ci vogliono 100 tentativi e non sfruttiamo la seconda palla. Forse dovremmo dividere i compiti (e il palazzo) tra le due sfere di cristallo in intervalli... basta, ho già detto troppo.
A presto
Ob
Why are numbers beautiful? It’s like asking why is Beethoven’s Ninth Symphony beautiful. If you don’t see why, someone can’t tell you. I know numbers are beautiful. If they aren’t beautiful, nothing is. - P. Erdös
Come idea di partenza avevo fatto il tuo stesso ragionamento, ma poi mi sono accorto di aver sbagliato... c'è un metodo ancora più veloce!Oblomov ha scritto: Giusto un hintino: Se procediamo partendo da terra e salendo di un piano alla volta buttando ogni volta la palla a terra siamo sicuri di farcela... ma ci vogliono 100 tentativi e non sfruttiamo la seconda palla. Forse dovremmo dividere i compiti (e il palazzo) tra le due sfere di cristallo in intervalli... basta, ho già detto troppo.
Appassionatamente BTA 197!
Mi sembra che il numero minimo di tentativi sia 51 (nel caso più sfortunato).
Chiamiamo P il piano più alto da cui non si romperà la palla. Faccio un tentativo per tutti i piani pari, e quando la palla si romperà ad un certo piano t, provo a lanciare la seconda palla dal piano t-1: se si romperà, allora P è uguale a t-1, altrimenti è uguale a t.
Poichè ho solo due palle di vetro a disposizione, mi sembra che non si possano usare altre strategie, come ad esempio quella precedente per ogni piano multiplo di un numero n diverso da 2 (servirebbero n palle di vetro), nè dividere di volta in volta i piani rimasti in 2 intervalli (cioè faccio un tentativo al 50°, poi se non si rompe al 75°, poi, se si rompe, a metà tra il 50° e il 75°, altrimenti a metà tra il 75° e il 100°, e così via), perchè servirebbero 7 (giusto?) palle di vetro.
Spero di non avere detto delle cavolate...
Chiamiamo P il piano più alto da cui non si romperà la palla. Faccio un tentativo per tutti i piani pari, e quando la palla si romperà ad un certo piano t, provo a lanciare la seconda palla dal piano t-1: se si romperà, allora P è uguale a t-1, altrimenti è uguale a t.
Poichè ho solo due palle di vetro a disposizione, mi sembra che non si possano usare altre strategie, come ad esempio quella precedente per ogni piano multiplo di un numero n diverso da 2 (servirebbero n palle di vetro), nè dividere di volta in volta i piani rimasti in 2 intervalli (cioè faccio un tentativo al 50°, poi se non si rompe al 75°, poi, se si rompe, a metà tra il 50° e il 75°, altrimenti a metà tra il 75° e il 100°, e così via), perchè servirebbero 7 (giusto?) palle di vetro.
Spero di non avere detto delle cavolate...
Mi muovo dal basso verso l'alto.
Facendo vari tentativi, suppongo di saltare qualche piano. Diciamo che salto $ n $ piani. Cioè $ n-1 $ sono i piani che intercorrono tra un piano di lancio e il successivo.
Esempio: dal piano $ 1 $, il successivo sarà il piano $ n+1 $.
Parto da un piano $ x $ in modo da arrivare a $ 100 $ precisi. Dunque $ 100\equiv x \pmod{n} $.
Il caso peggiore si verifica quando, il piano ricercato è il $ 99 $.
I piani da testare uno per uno nell'intervallo tra il penultimo e l'ultimo piano di prova sono $ n-1 $.
Posso scrivere invece 100, come $ 100=kn+x $ quindi i piani di prova sono $ k+1 $ perchè $ k $ può anche essere 0.
Piani di prova: $ k+1 $
Piani da testare, nella configurazione peggiore: $ n-1 $
Piani totali: $ k+n $
Quant'è il minimo di $ k+n $?
$ \displaystyle k=\frac{100-x}{n} $, dunque, senza toccare $ n $ più di tanto, $ k $ è minimo, quando $ x=n, \ k=\displaystyle \frac{100}{n}-1 $
Con un pò di prove su $ n $ si vede che il minimo di $ k+n $ è 24.
edit: perchè io ho trovato 24 e Julio assicura 14?
Facendo vari tentativi, suppongo di saltare qualche piano. Diciamo che salto $ n $ piani. Cioè $ n-1 $ sono i piani che intercorrono tra un piano di lancio e il successivo.
Esempio: dal piano $ 1 $, il successivo sarà il piano $ n+1 $.
Parto da un piano $ x $ in modo da arrivare a $ 100 $ precisi. Dunque $ 100\equiv x \pmod{n} $.
Il caso peggiore si verifica quando, il piano ricercato è il $ 99 $.
I piani da testare uno per uno nell'intervallo tra il penultimo e l'ultimo piano di prova sono $ n-1 $.
Posso scrivere invece 100, come $ 100=kn+x $ quindi i piani di prova sono $ k+1 $ perchè $ k $ può anche essere 0.
Piani di prova: $ k+1 $
Piani da testare, nella configurazione peggiore: $ n-1 $
Piani totali: $ k+n $
Quant'è il minimo di $ k+n $?
$ \displaystyle k=\frac{100-x}{n} $, dunque, senza toccare $ n $ più di tanto, $ k $ è minimo, quando $ x=n, \ k=\displaystyle \frac{100}{n}-1 $
Con un pò di prove su $ n $ si vede che il minimo di $ k+n $ è 24.
edit: perchè io ho trovato 24 e Julio assicura 14?
A questo punto metto la mia.
Parto dal n=14 piano. Si rompe?
Si->riparto dal primo e faccio uno alla volta finchè non lo trovo, al massimo 14 lanci.
No-> vado al piano n+n-1=27 piano. Si rompe, torno al 15 e li faccio uno alla volta, ancora al massimo 14, non si rompe vado al 27+12=39 e ripeto. In questo modo non faccio mai più di 14 lanci. Con questo metodo, 14 è il minimo, infatti con 13 arrivo dopo 13 lanci a 91, per poi finire i controlli arrivo al massimo a 22. Mentre con 14 dopo 11 lanci sono a 99, quindi riesco a controllare tutti i piani.
Parto dal n=14 piano. Si rompe?
Si->riparto dal primo e faccio uno alla volta finchè non lo trovo, al massimo 14 lanci.
No-> vado al piano n+n-1=27 piano. Si rompe, torno al 15 e li faccio uno alla volta, ancora al massimo 14, non si rompe vado al 27+12=39 e ripeto. In questo modo non faccio mai più di 14 lanci. Con questo metodo, 14 è il minimo, infatti con 13 arrivo dopo 13 lanci a 91, per poi finire i controlli arrivo al massimo a 22. Mentre con 14 dopo 11 lanci sono a 99, quindi riesco a controllare tutti i piani.
Sì 14 è giusto!
Praticamente avevo trovato, come ha fatto julio14, il numero 14 (vedi julio era proprio fatto per te questo problema
) e poi per i numeri inferiori ho dimostrato che non si può arrivare a 100 seguendo il metodo proposto da julio che tra altro è quello che sfrutta al massimo la differenza di piani che posso saltare tra un tentativo e l'altro con un numero di tentativi fissato...
Praticamente avevo trovato, come ha fatto julio14, il numero 14 (vedi julio era proprio fatto per te questo problema
) e poi per i numeri inferiori ho dimostrato che non si può arrivare a 100 seguendo il metodo proposto da julio che tra altro è quello che sfrutta al massimo la differenza di piani che posso saltare tra un tentativo e l'altro con un numero di tentativi fissato...Appassionatamente BTA 197!
tu dove hai trovato questo quesito? Compare su un simpatico libro di quesiti, ma so che non e' piu' reperibile (ma io ce l'ho 
)
)impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
@SkZ
L'hanno proposto durante uno stage (non olimpionico) di matematica che si è svolto a Pracatinat.
@julio14
(Spero che tu lo capisca...è tardi e ho la mente molto incasinata)
Io avevo ragionato più o meno così (l'idea di partenza l'ho avuta da un mio compagno)
Sia k il numero dei tentativi cercato
Dimostriamo che
1) Per il caso k=14 è possibile
2) Non esiste nessun caso k<14 soddisfacente le condizioni iniziali
Il primo punto è già praticamente dimostrato da te.
Per il secondo punto notiamo che se esiste un numero di tentativi minore di 14 con il quale possiamo individuare il piano cercato allora il primo piano che proviamo è per forza k-esimo (così sfruttiamo al massimo il valore k e quindi è l'unico metodo più vantaggioso), se si rompe allora dobbiamo controllare tutti i (k-1) piani sotto, altrimenti si sale sul piano 2k-1, (si nota che salendo sul (2k-1)esimo piano abbiamo già utilizzato due tenativi e quindi sono rimasti k-2 tentativi infatti fra 2k-1 e k c sono proprio k-1 piani) e da lì ripetere il gioco.
Notiamo adesso anche che dato un numero k, il piano più alto che può salire, in modo che a ogni piano che sale può sempre individuare il piano cercato se la palla si rompe, è $ $k+ \frac{k*(k-1)}{2} $
Per k=13 il piano più alto che può salire è quindi 91 e quindi non riuscirà a individuare il piano richiesto (altrimenti farebbe più di 13 tentativi!)
Se per k=13 non è possibile a maggior ragione anche per i valori minori di 13 non è possibile. Per cui abbiamo dimostrato che il 14 è proprio il valore minimo.
L'hanno proposto durante uno stage (non olimpionico) di matematica che si è svolto a Pracatinat.
@julio14
(Spero che tu lo capisca...è tardi e ho la mente molto incasinata)
Io avevo ragionato più o meno così (l'idea di partenza l'ho avuta da un mio compagno)
Sia k il numero dei tentativi cercato
Dimostriamo che
1) Per il caso k=14 è possibile
2) Non esiste nessun caso k<14 soddisfacente le condizioni iniziali
Il primo punto è già praticamente dimostrato da te.
Per il secondo punto notiamo che se esiste un numero di tentativi minore di 14 con il quale possiamo individuare il piano cercato allora il primo piano che proviamo è per forza k-esimo (così sfruttiamo al massimo il valore k e quindi è l'unico metodo più vantaggioso), se si rompe allora dobbiamo controllare tutti i (k-1) piani sotto, altrimenti si sale sul piano 2k-1, (si nota che salendo sul (2k-1)esimo piano abbiamo già utilizzato due tenativi e quindi sono rimasti k-2 tentativi infatti fra 2k-1 e k c sono proprio k-1 piani) e da lì ripetere il gioco.
Notiamo adesso anche che dato un numero k, il piano più alto che può salire, in modo che a ogni piano che sale può sempre individuare il piano cercato se la palla si rompe, è $ $k+ \frac{k*(k-1)}{2} $
Per k=13 il piano più alto che può salire è quindi 91 e quindi non riuscirà a individuare il piano richiesto (altrimenti farebbe più di 13 tentativi!)
Se per k=13 non è possibile a maggior ragione anche per i valori minori di 13 non è possibile. Per cui abbiamo dimostrato che il 14 è proprio il valore minimo.
Appassionatamente BTA 197!
