Il problema delle due uova

[Quelo]

Tratto dalle pagine di BASE Cinque

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!

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.

SE&O

[infinito]

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

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

[Gianfranco]

Complimenti a Gaspero e a Quelo.
La soluzione di Quelo è buona, ma quella di Gaspero credo che sia la migliore fra quelle note.
Sarebbe bello accennare alla dimostrazione che meglio di così non si può fare.

Ah, Gaspero, grazie anche per le precisazioni.

Gianfranco

[infinito]

Oggi (ad un'ora più "cristiana") ho fatto i calcoli (poi stanotte ci ho rimesso le mani, arrivando alla stessa ora ...):
per il numero massimo di lanci (che era la risposta richiesta), ovviamente la risposta è "14".
Per il numero medio di lanci (con il mio metodo) la risposta è circa 10,366 (e non «poco più di 7», come avevo detto stanotte), invece con quello di Quelo viene circa 10,891 quindi valori abbastanza vicini (o almeno molto più vicini del numero massimo di lanci).

Ho avuto difficoltà nel calcolo della media, ed ho fatto errori, perché avevo considerato che c'erano 100 diverse possibilità, invece sono 101: infatti l'uovo può rompersi ad uno qualunque dei 100 piani, ma anche non rompersi affatto, come dire «più di 100», indicabile con «101».

Per chi vuole controllare il calcolo: sotto riporto il numero di lanci necessari (con il "mio" metodo) per ogni piano (dal 1° al 100°, dove su ogni riga ho messo quelli fatti dopo la rottura del primo uovo, a parte l'ultimo):

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, (dal 1° al 14°)
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, (dal 15° al 27°)
4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, (dal 28° al 39°)
5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 14, (dal 40° al 50°)
6, 7, 8, 9, 10, 11, 12, 13, 14, 14, (dal 51° al 60°)
7, 8, 9, 10, 11, 12, 13, 14, 14, (dal 61° al 69°)
8, 9, 10, 11, 12, 13, 14, 14, (dal 70° al 77°)
9, 10, 11, 12, 13, 14, 14, (dal 78° al 84°)
10, 11, 12, 13, 14, 14, (dal 85° al 90°)
11, 12, 13, 14, 14, (dal 91° al 95°)
12, 13, 13, (dal 96° al 98°)
13, 13 (dal 99° al 100°)
13 (oltre il 100°, come dire "101°")

Sarebbe bello accennare alla dimostrazione che meglio di così non si può fare.

Pensavo di non fare la dimostrazione ..., ma poi ho letto che non la chiedevi, ma hai desiderato un "accenno" ...

Beh, allora sono abbastanza chiare le seguenti "cose":

- si deve procedere "in qualche maniera" dal basso verso l'alto: una volta che l'uovo si è rotto (e quindi so che il piano cercato è minore o uguale a quello di rottura) non può essere più utilizzato allo scopo, per cui si deve aver già contollato quelli sotto (oppure si controllano con l'altro uovo).

- con il metodo "semplice" (si inizia dal primo piano e si prosegue verso l'alto di piano in piano, si ha un massimo di 100 tentativi: troppi.

- ne segue che per ridurre il numero conviene usare il metodo di testare con un uovo alcuni piani, e poi con l'altro i piani "inframmezzati" (questa parte della dimostrazione non mi convince: potrebbero esserci altri metodi a cui non ho pensato).

- fissato il numero massimo di lanci n (il valore richiesto dal testo), se il primo uovo si rompe ad un piano p , restano n-p tentativi da fare con il secondo uovo , per cui «più è grande p, meno tentativi restano da fare», quindi "naturalmente" (nel senso di «il modo naturale è ...») il numero dei piani che si salta (quelli da testare con il secondo uovo) è via via decrescente, circa ogni volta uno meno (se aumenta di 1 il valore di p, diminuisce di 1 il numero di piani saltati)

- se si diminuisce "troppo" si corre il rischio di non arrivare ad esaurire tutti i 100 piani, e quindi di non riuscire nell'intento (per cui si dovrebbe aumentare il valore n).

- per sapere quanti piani vanno testati con il primo uovo si può procedere così: si inizia dal 100 piano (che va comunque testato), poi si prende il valore minimo dei piani da testare con il 2° uovo, che è 0 (cioè non si testano).
Quindi con il 1° uovo si testa il 99°, e con il secondo se ne tersta uno di più, cioè 1 (il 98°).
Poi con il 1° uovo si testa il 97° e con il 2° i piani 96° e 95°.
Poi 94° e 93°, 92°, 91°. e così via.
Io l'ho fatto, ed ho trovato, per il 1° uovo, i piani 9°, 22°, 34°, 45°, 55°, 64°, 72°, 79°, 85°, 90°, 94°, 97°, 99°, 100°, per cui n=14 .

- poiché il primo salto di piani è solo 9, mentre avrei la disponibilità di saltarne 14, posso scegliere se partire dal 100 e procedere come ho appena spiegato, oppure partire da 14, e poi procedere analogamente (ma verso l'alto) con 13, 12, 11, ... piani, oppure posso cercare di fare una cosa intermedia.

- con la seqeuenza scritta sopra (9°, 22°, 34°...) ottengo che la media è circa di 10.446, mentre con quella che ho proposto io ottengo 10.336, e "mi sembra" che con altre scelte aumenti di un capellino.

Spero che come "accenno" basti.

[Pasquale]

...."da quale altezza massima (misurata in piani)"....dice il testo, e penso che sarebbe meglio considerare i piani come al di sopra del piano terra, così che se un uovo si rompe al 1° piano, possiamo dire che si è è rotto al 1° piano; in sostanza ci sono davvero 100 piani da valutare.
Se il 1° piano lo consideriamo a terra, non ci sarà mai un uovo che possa rompersi al 1° piano (se l'uovo sta al piano terra, più in basso non può andare) e dovremmo considerare il 100° piano come 99°; chi ce lo fa fare?
Ha ragione Gaspero quando dice che nel linguaggio comune ( ed anche catastale) esiste un piano terra e che quello subito sopra si chiama 1° e non 2°. Insomma se avessimo un solo uovo, dovremmo fare 100 lanci.

[infinito]

Se il 1° piano lo consideriamo a terra, non ci sarà mai un uovo che possa rompersi al 1° piano (se l'uovo sta al piano terra, più in basso non può andare) e dovremmo considerare il 100° piano come 99°; chi ce lo fa fare?

dicendo che si lascia cadere un uovo dal piano terreno, intendo (salvo diverse indicazioni) che lo si lascia andare dall'altezza a cui si trovano le mani, e in genere (dipende soprattutto da che cosa c'è dove tocca "terra") si rompe, se un uovo cade sul cemento o su mattonelle.
Inoltre se il testo prevede che un uovo possa non rompersi cadendo dal 100° piano, possiamo anche pensare che possa rompersi cadendo dal piano 0, basta pensare che l'uovo non riesca a resistere al proprio peso.

(Mi piacciono queste questioni di pensiero laterale)