Olimpiadi della Matematica Torino - OliMaTO - Forum

Propongo questo giochino semplice semplice (è una domanda fatta ad un candidato per una delle aziende della Silicon Valley), il livello è proprio $0$

Avete due uova (mi raccomando, soltanto due) indistinguibili e siete in un palazzo di esattamente $100$ piani, contando il piano-terra. Sapete che esiste un piano limite a partire dal quale, ogni uovo che lanciate si rompe. Dovete trovare qual è il minimo del numero massimo di lanci che dovete compiere per individuare tale piano. (e.g. se il piano limite è il $100$, la strategia brutale è provare piano per piano, e quindi con $99$ lanci si ottiene, ma questa non è chiaramente la strategia migliore, ne dovete trovare una che permetta di fare sempre un certo numero di lanci, ed esso deve essere il minimo possibile!)

Bisogna anche dimostrare che la nostra idea è la migliore possibile? Intuitivamente la strategia migliore direi che è sempre dimezzare l'intervallo, certo che dimostrarlo forse è più difficile (o sto dicendo una caxxata? )

Ovvio! Devi dimostrare che quello è effettivamente il minimo. Mhh, che intendi? Per capirci, quale pensi sia il minimo facendo bisezione tante volte? (se non ho capito male l'algoritmo a cui hai pensato è quello di ricerca binaria)

Il minimo facendo bisezione dovrebbe essere 7 se non ho fatto una svista megagalattica nei conti, però non saprei dirti perchè non si può fare con 6

Uhm, magari ho una svista io, ma hai solo due uova: se il primo si rompe al piano [tex]50[/tex] (il piano terra è il piano [tex]1[/tex], per comodità) suppongo il tuo algoritmo imponga che il secondo venga lanciato dal piano [tex]25[/tex], e se si rompe pure questo come fai a stabilire quale sia il piano limite?

Tanto per non rendere questo un solo post di "critica":

Sì, come fa giustamente notare Gizeta, ricerca binaria non funziona proprio. Ti assicuro che il minimo non è $7$ (ma proprio mai nella vita ). Già il suo hint è più che sufficiente, dato il livello

Avevo perso di vista che fossero solo due uova, perdonatemi

Con l'hint mi sembra si possa generalizzare a $k$ uova senza infinito fastidio!

Yep, ed anche ad $m$ piani volendo! Ma fino ad ora nessuno che posta questo benedetto minimo

Allora: assumiamo che "lanciare un uovo dal piano [tex]x[/tex]" voglia dire che tale uovo passa per il piano [tex]x[/tex]; consideriamo, inoltre, che il piano limite è indubbiamente [tex]\le 100[/tex], quindi ogni uovo lanciato dal piano [tex]100[/tex] deve inevitabilmente rompersi, segue con facili conti che l'uovo si rompe se lanciato da qualsiasi piano in quanto una volta lanciato dal piano [tex]100[/tex] passa per qualsiasi piano, e quindi in ogni caso il piano limite è il piano [tex]1[/tex].
In definitiva, mi basta un lancio e un solo uovo.
Banali le varie generalizzazioni.