Piastrellatura di rettangoli
Hai due enigmi. Per un rettangolo 1xn, in quanti modi puoi riempirlo con un mix di quadrati 1x1 e rettangoli 1x2? Per un rettangolo 2xn, in quanti modi puoi riempirlo con rettangoli 1x2?
LA SFIDA
Perché questi due enigmi danno le stesse risposte? Quali sono le risposte quando i rettangoli da riempire sono lunghi 10? E quando sono lunghi 20?
ESPLORAZIONE
In che modo questi due problemi sono simili tra loro e ai puzzle precedenti? Come cambiano le cose nel puzzle 1xn se usiamo pezzi 1x1 e 1x3? Come cambiano le cose nel puzzle 1xn se usiamo pezzi 1x1, 1x2 e 1x3?
Note
LA SFIDA
Capire come applicare i risultati precedenti a una parte o all'intero problema di un nuovo puzzle è un'abilità molto utile.
Questi due puzzle sono esattamente identici. I pezzi verticali nel rettangolo 2xn corrispondono ai pezzi 1x1 nel rettangolo 1xn, e i pezzi orizzontali nel rettangolo 2xn corrispondono ai pezzi 1x2 nel rettangolo 1xn. Quindi, in realtà non c'è alcuna differenza tra i due puzzle.
Inoltre, il puzzle rettangolare 1 x n è esattamente come il puzzle a passi di "Fibonacci - 2". Procedere di un passo alla volta è come inserire un quadrato 1 x 1, e procedere di due passi alla volta è come inserire un rettangolo 1 x 2. I due puzzle sono identici, quindi l'analisi e i risultati sono gli stessi.
ESPLORAZIONE
Se usiamo rettangoli 1x1 e 1x3, molte cose cambiano. Osserviamo i primi valori e consideriamo come vengono calcolati. Otteniamo 1, 1, 2, 3, 4, 6 e 9 per i primi valori. In generale, il valore successivo è la somma del valore corrente e di quello di due passi prima. È abbastanza semplice da calcolare, ma non si tratta più della successione di Fibonacci.
Se usiamo 1 per 1, 1 per 2 e 1 per 3, le cose cambiano in modo ancora più drastico. Ora i primi valori sono dati da 1, 2, 4, 7, 13 e 24. Il valore successivo nella sequenza è la somma dei tre valori precedenti.
Le sequenze come questa, che definiscono i termini successivi tramite una formula che coinvolge i termini precedenti, sono chiamate sequenze ricorsive. I numeri di Fibonacci non sono l'unica sequenza ricorsiva, ma sono probabilmente la più famosa.