Categorie: Matematica Storia della Scienza
Tags: grattacielo di 100 piani quiz uova
Scritto da: Vincenzo Zappalà
Commenti:20
Rompiamo le uova nel ... grattacielo ***
Un altro simpatico quiz che ci permetterà di introdurre alcuni concetti di estrema importanza, che abbiamo già trattato (ma non vi dico certo dove e quando!). L'importante è avere due uova (piuttosto robuste) e non avere paura di ... romperle.
Il nostro campo di gara è un grattacielo di 100 piani (non esiste il pianterreno!).
Un aperitivo per cominciare a pensare
Chiamiamo PIANO CRITICO il primo piano in cui l'uovo si rompe. Immaginiamo di avere soltanto un uovo a disposizione. Vogliamo sapere qual è il minimo numero di lanci che si devono effettuare per determinarlo con sicurezza il PIANO CRITICO, anche nelle condizioni peggiori.
Facciamo un esempio per chiarire meglio la situazione. Immaginiamo che il piano critico sia il quinto piano. Abbiamo solo un uovo a disposizione e una strategia potrebbe essere quella di cominciare a lanciarlo dal primo piano. Non si rompe? Bene, passiamo al secondo e via dicendo. Giunti al quarto piano l'uovo si salva ancora, ma salendo al quinto ecco che si rompe. Quanti lanci ho dovuto eseguire? cinque lanci (uno dal primo, uno dal secondo, uno dal terzo, uno dal quarto e uno dal quinto).
Sì, d'accordo... ma se il piano critico fosse il 52? Usando la stessa strategia di prima dovrei fare 52 lanci per avere la certezza di avere individuato il piano critico. Non parliamo poi se il piano critico fosse il 100. Dovrei effettuare proprio 100 lanci! Con questa strategia il minimo numero di lanci che dovremmo effettuare per avere la certezza di determinare il piano critico, anche nel caso peggiore, è proprio 100.
Un'altra strategia potrebbe essere quella di lanciare subito l'uovo dal piano 50. Se non si rompe potrei passare al 51, poi al 52 e via dicendo. Il caso peggiore sarebbe nuovamente il centesimo piano e avrei risolto il problema con soli 50 lanci? Assolutamente no! Se, infatti, l'uomo si rompesse già al cinquantesimo piano, saprei che devo scendere, ma non avrei più nessun uovo a disposizione!
Cominciate a pensare se esiste una strategia alternativa per riuscire ad avere la certezza di determinare il piano critico con meno di 100 lanci anche nelle condizioni peggiori. Fatto? Bene, possiamo passare al VERO quiz.
Un uovo in più
La domanda è sempre la stessa del caso precedente:
Qual è il minimo numero di lanci necessari per sapere con certezza assoluta qual è il PIANO CRITICO, anche nelle peggiori condizioni ?
Ovviamente, si chiede anche:
Quale strategia si deve utilizzare per minimizzare il numero di lanci necessari per darci la garanzia di trovare SEMPRE il piano critico, anche nelle peggiori condizioni?
Ovviamente, le due uova si comportano nello stesso identico modo: se se ne rompe uno, si rompe anche l'altro; se non si rompe il primo, non si rompe nemmeno il secondo.
Forza e coraggio...
N.B.: non è ammesso farsi le due uova al tegamino!
QUI la soluzione n°1
20 commenti
Insieme di Cantor di esponente 4.
le solite risposte senza spiegazione e, in questo caso, senza nemmeno una risposta. Dai Leandro, sei in un Circolo divulgativo dove si cerca di spiegare la Scienza a tutti (o quasi). Quindi strategia e risultato, please...
Spero di non rompere le uova..
Premetto che per me la soluzione di questo problema sarebbe da affidare ad un algoritmo da tradurre poi in linguaggio di programmazione. Sarò poi conciso.
Dobbiamo partire da un piano interno, altrimenti dobbiamo scorrere tutti i piani nel caso peggiore.
Indichiamo tale piano con n;
Se l’uovo si rompe, abbiamo un altro uovo per scendere fino a trovare il piano giusto. Altrimenti saliamo e lanciamo ancora il primo uovo. Di quanto saliamo ? intuitivamente di una quantità decrescente da n, per diminuire il numero dei tentativi con il secondo uovo. Sempre Intuitivamente, l’obiettivo è , se dobbiamo salire fino al 100°, di diminuire i tentativi fino a 1. D’altro canto, la somma di tutti incrementi, sommata a n deve essere >=100; quindi se supponiamo di decrementare in questo modo, n-1,n-2,…3,2,1 dobbiamo risolvere il problema:
n+ n-1+ n-2+.. 3+2+1>=100
applicando la formula di Gauss, questo si traduce in n(n+1)/2>=100
che porta ad un’equazione di secondo grado, e che dà come risultato 13,6. Quindi avendo a che fare con interi dobbiamo approssimare a 14. Si può partire dal 14°piano. Per arrivare al 100°, bastano di conseguenza 12 tentativi, come si può facilmente vedere. Ripeto : questo è un valore buono, ma non è dimostrato che sia il minore. Ci vuole per me un algoritmo, o qualche altra idea.
grazie Umberto...
ma il risultato non è il numero di tentativi, ma il minor numero di lanci (delle due uova), nel caso peggiore.
Il 12 che dici tu non è quel valore... Immagina che si rompa il primo uovo già al piano 14. Bene, devi usare il secondo per scendere fino a 1 o salire da 1 fino a 13. Nel primo caso se il piano critico fosse proprio il primo avremmo 13 lanci da fare con il secondo uovo e uno con il primo: totale 14. Nel secondo caso (salendo) ammettiamo che il piano critico sia il 13. Partendo da 1 dovremmo nuovamente fare 13 lanci con il secondo e uno con il primo: nuovamente 14. Ne segue che 12 non può essere il minimo numero nel caso peggiore (abbiamo già visto che esiste sicuramente il 14 e non è nemmeno detto che sia il peggior caso!).
scusa ho scritto 12 per 14.. io per tentativi intendo lanci..
A questo punto non so se ho capito bene il testo; se la soluzione migliore è per il 14° piano, che è il nostro n, poi salgo di n-1, poi n-2,..
la sequenza è questa:
14
13
27
12
39
11
50
10
60
9
69
8
84
7
90
6
95
5
99
4
se per esempio sono arrivato con due uova al 39, con 3 lanci poi lancio e si rompe il primo devo poi risalire di 11 per trovare il piano esatto; e 11+3=14; al 50 ci arrivo con 4 lanci, se lancio e si rompe resto con 10 10+4=14; a 60 arrivo con 5 lanci, poi scendo di 9, 9+5=14, ecc. ecc. <Con 14 sto dentro dappertutto.Dove è che sbaglio?
OK... il mio commento riguardava solo il 12... che doveva essere 14. A qualsiasi piano tu arrivi non cambia il numero di lanci totale ogni volta che si rompe il primo uovo e devi cercare nell'intervallo tra due suoi lanci consecutivi. Usiamo termini diversi, ma il succo è quello...
Io partirei dal piano 50 (a metà tra 1 e 100); poi se l'uovo si rompe proverei al piano 25 (metà di 50), altrimenti al 75 (a metà tra 50 e 100).
Dimezzando di volta in volta, al primo tentativo ho, nel caso peggiore, un intervallo di incertezza di 50 piani, al secondo di 25, al terzo 13 (se va male, altrimenti 12), poi 7, 4, 2 , 1, per un totale di 7 tentativi.
Es.
Lancio
Piano
Si rompe?
1
50
no
2
75
sì
3
62
no
4
69
sì
5
65
no
6
64
no
7
63
sì
caro Marco,
non è il caso peggiore... se lo lanci al 50 e si rompe, vai al 25... e se si rompe? hai finito le uova e non hai trovato un bel niente. Ma anche se non si rompesse...sai solo che è compreso tra 25 e 50. E se il piano critico fosse il 49? Come faresti a trovarlo con un uovo solo? Dovresti provare dal 26 fino al 49...
Forse la chiave del problema è l'asimmetria tra i due risultati del lancio.
Se faccio il primo lancio al piano L1, se l'uovo si rompe sono costretto a ripartire dal primo piano e risalire piano per piano fino ad arrivare, nel caso peggiore, al piano L1-2. Per un totale di L1-1 lanci.
Se l'uovo non si rompe posso invece risalire di più piani per fare un ulteriore tentativo. Se l'uovo si rompe devo tornare al piano L1+1 e risalire piano per piano. Se non si rompe posso risalire per più piani e così via.
La soluzione potrebbe essere quella di trovare il piano L1 che bilancia il numero di lanci da fare se l'uovo si rompe e se l'uovo non si rompe. Se l'uovo non si rompe, il piano successivo potrebbe essere trovato con lo stesso criterio, cioè risalendo sempre della stessa frazione dei piani restanti.
Una prima approssimazione di questa frazione potrebbe essere il 18%, cioè fare il primo lancio al 18° piano. Il numero di lanci nel caso peggiore sarebbe quindi 17. Ci può essere qualche aggiustamento da fare per le conversioni ad intero e per ottimizzazioni che evitano il lancio finale.
caro Fabry, che piacere sentirti!
comunque, si può ottenere un risultato migliore ...
Ho sviluppato un software che trova il risultato analizzando tutte le combinazioni. Dà come risultato proprio 14, come affermavo sopra.. E' un po' dura descrivere le argomentazioni di costruzione nell'algoritmo in un commento. Se non hai niente in contrario, dopo che avrai dato la tua soluzione , potrei scrivere la mia soluzione software alternativa.
senz'altro Umberto! Pensavo di pubblicare la soluzione domani. Tu quando sarai pronto?
Ciao Vincenzo,
Il minimo numero di lanci nel caso peggiore è 13
La logica e’ trovare il passo uniforme iniziale che garantisce il minimo numero di lanci. Si può fare trovando il minimo della funzione 100/n+n-1, dove n è il passo. La soluzione è 10. A questo punto si possono utilizzare passi sempre più piccoli dimezzando ad ogni iterazione l’intervallo. Ad esempio si può utilizzare prima passo 4 poi 3 poi 2 e infine 1. Ad esempio faccio il lancio al 10 piano, poi a passo 10 fino al 90. A questo punto uso passo 4 arrivando a 94. Ne rimango 6. Uso come passo la sua metà e sono a 97. Poi faccio un lancio dopo due piani e sono a 99. Se l’uovo non si è rotto il piano critico è il 100 ma in questo scenario il caso peggiore si verificherebbe al piano 98 o 99. In tali casi arrivati al 99 avrei la rottura di un uovo e dovrei fare un lancio al piano 98 per avere la certezza su quale dei due è critico.
La stessa soluzione si avrebbe se arrivati al piano 90 con lanci ogni 10 si passasse a fare lanci a passi prima 5 poi 2 ancora 2 e poi 1 per discriminare tra 98 e 99.
caro Mariano,
la tua strategia sembrerebbe buona, ma hai il rischio di rimanere senza uova!
Immagina di lanciare l'uovo E al piano 70: non si rompe. Poi all'80: si rompe. Ti è rimasto un solo uovo (R) e se lo fai cadere al 74 e si rompe? Qual'è il piano critico? Può essere il 71, il 72 o il 73, ma non hai più uova per provarlo.
scusa, ho problemi di lavandino.. intasato. Non mi ci vuole tanto, ma io direi di pubblicarla il giorno dopo la tua, non assieme per non far confusione.
perfetto... io l'ho pubblicata stamattina. Tu puoi andare quando vuoi, o domani o dopodomani... senza problemi.
Auguri per il lavandino!!!
Mi era sfuggito il fatto che le uova a disposizione fossero solo 2.
scusa Marco se ti ho chiamato Mariano... ho fatto un mix...
Nessun problema Vincenzo