 |
Questa pagina è stata trascritta, formattata e riletta. | |
| 178 | Maurizio Codogno |
•• ••• ••••• ••••••• ••••• ••• ••
97. Test di resistenza
Supponiamo che il palazzo abbia n piani e di lanciare un uovo dal piano p. I casi sono due: o l’uovo si rompe, o non si rompe. Se si rompe, a questo punto dobbiamo provare a lanciare il prezioso secondo uovo dal primo piano al piano p−1, con un totale di p lanci nel caso peggiore. Se non si rompe, abbiamo usato un lancio ma ci rimangono solo n–p piani da testare.
Se quindi consideriamo la funzione F(l) che misura quanti piani si possono testare con due uova e l lanci, dobbiamo scegliere il piano dove fare il primo lancio in modo tale che F(l−1) = n−l; in questo modo riusciamo infatti a equilibrare i test da fare “più in alto” e quelli da fare “più in basso”. Ora, F(1) = 1 (occorre per forza testare il primo piano). In generale, F(l) – F(l−1) = l; quindi andando man mano indietro abbiamo che F(l) è la somma dei numeri da 1 a l, cioè l(l+1)/2. Facendo un po’ di conti, F(13) = 91 e F(14) = 105; il nostro test richiederà al più 14 lanci.
Post Scriptum
Se invece di scrivere il problema sotto forma di giochino l’avessi scritto nel modo prediletto da chi prepara i libri di testo (“Dimostrate che con due uova e l lanci, blablabla, potete discriminare tra l(l+1)/2 piani diversi”) avreste trovato un tipico esempio di problema che si risolve per mezzo dell’induzione, come raccontato nel problema 69. In questo caso l’applicazione sarebbe stata molto semplice, visto che il caso di un singolo lancio è immediato e quello generale si ricava mostrando come abbiamo fatto noi che conviene fare il primo lancio all’n-simo piano. Però bisogna dire che l’induzione, pur essendo un metodo molto potente, è anche piuttosto noiosa, tanto che non mi stupirei se qualcuno avesse scritto un programma di intelligenza artificiale che riesce a risolvere problemi per induzione. Spero che nascondendola in questo modo il procedimento sia risultato più piacevole!
•• ••• ••••• ••••••• ••••• ••• ••
