[BASE Cinque - Appunti di Matematica ricreativa]
Metodo ottimo per scoprire da quale altezza massima un uovo può cadere senza rompersi
Avete due uova e potete accedere a un palazzo di 100 piani.
Le uova di questo problema sono tutte uguali e hanno esattamente la stessa resistenza: un uovo vale l'altro.
Dovete stabilire da quale altezza massima (misurata in piani) un uovo può cadere senza rompersi.
Le uova potrebbero rompersi cadendo dal primo piano, o potrebbero anche resistere a una caduta dal centesimo piano. Non avete altre informazioni.
Quindi, per trovare la risposta non vi resta che procedere per tentativi, lanciando un uovo da piani sempre più alti finché non si rompe.
Qual è il maggior numero di lanci da fare per trovare il piano più alto?
In altre parole, qual è il modo più efficiente di far cadere le uova per trovare la risposta?
Ricordate che, per risolvere il problema, avete soltanto due uova da rompere!
Nota.
Sembra che questo problema sia una delle Google interview questions
(domande poste ai colloqui di lavoro presso Google).
Riporto due risposte dal Forum in attesa di una analisi più dettagliata e di una eventuale generalizzazione.
Se ho capito bene si tratta di minimizzare il numero massimo di lanci necessari per scoprire da che piano di rompono le uova.
Se avessi un solo uovo, non avrei altra scelta che provare tutti i piani (se salto qualche piano e l'uovo si rompe, non saprò mai se l'uovo si sarebbe rotto a un piano più basso) Nel caso peggiore (uovo che si rompe al 100° piano o che non si rompe affatto) devo fare 100 lanci, con una media di 51 lanci per uovo se avessi diverse uova con resistenza differente
Avendo 2 uova a disposizione posso adottare questa strategia: lancio il primo uovo ogni x piani finché non si rompe (oppure resiste) Se si rompe provo ad uno a uno i piani intermedi con il secondo uovo.
Con questa strategia il sistema più efficiente è lanciare il primo uovo ogni 10 piani con un numero massimo di lanci pari a 19 (uovo che si rompe al 99° piano) e una media di 10 lanci per coppia di uova (se ne avessi diverse da testare).
Le strategie a 8, 9, 11, 12 e 13 piani danno sempre un numero massimo di lanci pari a 19 ma una media lanci leggermente superiore a 10.
(Quelo - Sergio)
Cita: Avete due uova e potete accedere a un palazzo di 100 piani.
Forse sono io ... ma in questo tipo di problemi non mi è mai chiaro quanti sono effettivamente i piani, perchè nel linguaggio comune a volte si intende "più il piano terreno" (in palazzo "di due piani" spesso si intende che ne ha due oltre al pianterreno).
Ma diamo per scontato che si tratti di 100 piani compreso il pianterreno, cioè che il 1° piano sia il piano terreno (questo è decisamente diverso dal linguaggio ordinario).
Cita: Con questa strategia il sistema più efficiente è lanciare il primo uovo ogni 10 piani con un numero massimo di lanci pari a 19 (uovo che si rompe al 99° piano) e una media di 10 lanci per coppia di uova (se ne avessi diverse da testare)
Mi pare che questo non sia il sistema più efficiente. Scusatemi, ma non ho voglia di fare calcoli, e dò solo un po' di suggerimenti intuitivi (spero che siano corretti).
Mi pare che con questa strategia se l'uovo si rompe ai "primi" piani, in media piani si facciano meno lanci che se si rompe anegli ultimi piani, per cui credo che sia più conveniente saltare inizialmente più piani, e alla fine meno.
Inoltre non conviene iniziare dal primo piano, ma, come dire, conviene escludere il primo lancio. Quindi "ad occhio" proporrei, per il primo uovo, i seguenti piani:
14°, 27°, 39°, 50°, 60°, 69°, 77°, 84°, 90°, 95°, 98°, 100°.
Ovviamente per il secondo uovo, se il primo si rompe ad un piano, faccio la prova a partire dal piano immediatamente superiore all'ultimo in cui non si era rotto (se si rompe già al 14° faccio le prove a partire dal 1° piano), se non si rompe nemmeno al 100° non faccio altre prove.
Mi pare che il numero massimo di prove sia 14. La media che dovrebbe essere di poco superiore a 7 (non l'ho calcolata ... ma il testo non lo richiedeva).
(Infinito - Gaspero)
Data creazione: giugno 2012
Ultimo aggiornamento: luglio 2012
xhtml 1.1
Sito Web realizzato da Gianfranco Bo