Hai 2 uova identiche e un edificio di 100 piani. Vuoi trovare il piano più basso da cui un uovo lanciato si rompe (potrebbe essere qualsiasi piano da 1 a 100, o nessuno).
Le uova sono identiche: se una si rompe dal piano X, anche l'altra si romperebbe. Se una sopravvive, anche l'altra sopravvivrebbe.
Qual è il numero minimo di lanci nel caso peggiore per determinare con certezza il piano critico?
Con 1 solo uovo dovresti andare piano per piano (fino a 100 lanci). Con 2 uova puoi "saltare" dei piani con il primo uovo. Ma se il primo si rompe, devi controllare i piani sotto uno a uno. Come bilanciare?
Il numero minimo di lanci nel caso peggiore è 14.
Strategia: lancia il primo uovo dai piani 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 (intervalli decrescenti: 14, 13, 12, ...).
Perché funziona:
- Se il primo uovo si rompe al piano 14, hai 13 piani da controllare col secondo uovo (1-13) = 1 + 13 = 14 lanci
- Se si rompe al piano 27, hai già fatto 2 lanci e 12 piani da controllare (15-26) = 2 + 12 = 14 lanci
- E così via: ogni scenario richiede al massimo 14 lanci
Matematicamente: cerchiamo n tale che n + (n-1) + (n-2) + ... + 1 >= 100. Questo dà n(n+1)/2 >= 100, quindi n >= 14.