I problemi di Fibonacci: Le mele

By Abhijit Tembhekar from Mumbai, India (Nikon D80 Apple) [CC-BY-2.0], via Wikimedia Commons

Con questa nuova puntata dei Problemi di Fibonacci affrontiamo una questione mangereccia legata a uno dei frutti più noti sin dai tempi della candida Biancaneve, la mela. Il primo quesito che vi propongo, sempre tratto dal libro curato da Geronimi, è Di colui che è andato nel giardino del piacere a cogliere delle mele.

Un uomo, per entrare nel giardino del piacere, deve attraversare 7 porte. Per uscirne, deve invece pagare i guardiani delle porte.
Nel giardino, però, raccoglie le mele che gli serviranno per pagare i guardiani.
Uscendo, deve dare al primo guardiano metà delle mele raccolte più un'altra mela; al secondo deve dare metà delle mele rimastegli più un'altra mela.
Così per tutti gli altri 5 guardiani: a ognuno deve dare la metà delle mele rimaste, più un'ulteriore mela.
All'uscita, dopo la settima porta, gli è rimasta una sola mela.
Quante mele aveva raccolto nel giardino?

La soluzione del problema è un sistema perfetto per un algoritmo. Fibonacci affronta la risoluzione in due modi, entrambi a passi successivi. Nel primo si eseguono calcoli numerici ad ogni passo e si calcola quante mele avesse l'uomo prima di attraversare ogni porta.
Ad esempio, partendo dal fatto che l'uomo alla fine esce con 1 sola mela, si calcola che, prima della settima porta, il numero di mele fosse: \[(1+1) \cdot 2 = 4\] e prima della sesta porta \[(4+1) \cdot 2 = 10\] e così via fino ad arrivare al numero di mele raccolte.
Nel secondo metodo, invece, ad ogni passo si modifica una equazione fino all'ottenimento di quella risolutiva.
La prima equazione della serie sarà: \[\frac{x}{2} + 1\] che rappresenta il numero di mele dare al primo guardiano, cui segue \[x-\frac{x}{2} - 1 = \frac{x-2}{2}\] che è il numero di mele rimaste dopo la prima porta, dalle quali andranno calcolate quelle da consegnare al secondo guardiano \[\frac{x-2}{2} - \left ( \frac{x-2}{4} + 1 \right ) = \frac{x-6}{4}\] e così via.\\ Volendo usare metodi moderni, si può invece usare il foglio elettronico. Prima di tutto, però, dobbiamo scrivere come procede la serie delle mele:
Si parte dalle mele raccolte, $m_0$. Le mele date al primo guardiano saranno \[m_1 = \frac{1}{2} m_0 + 1\] mentre le mele date al secondo guardiano saranno \[m_2 = \frac{1}{2} \left (m_0 - m_1 \right ) + 1\] dove la differenza tra $m_0$ ed $m_1$ sono le mele rimaste all'uomo, e così via.
Se impostate correttamente le colonne che vi servono, troverete un indizio per la soluzione partendo dal caso di 0 mele raccolte. A quel punto dovete solo fare una somma opportuna delle opportune potenze di 2 che avrete visualizzato in questo modo!