Ricoprire un 2xn

[Karl Zsigmondy]

Generalizzando un problema della finale internazionale organizzata dalla FFJM.

In quanti modi si può ricoprire un rettangolo 2xn con dei quadrati 1x1 e dei rettangoli 2x1?

(Il problema in realtà chiedeva di ricoprire un 2x7)

[exodd]

La formula di ricorrenza si trova, ma quella chiusa è più ostica..

[sasha™]

La formula ricorsiva è per caso $a_n = a_{n-2} + 2\cdot\sum a_i$ ?

[exodd]

La formula ricorsiva è per caso $a_n = a_{n-2} + 2\cdot\sum a_i$ ?

Sì, è la stessa che è venuta a me..

[fph]

La formula di ricorrenza si trova, ma quella chiusa è più ostica..

Hint per trovare senza troppa fatica la formula chiusa da quella ricorsiva:

Testo nascosto:

Poni $A_n:=\sum_{i=0}^n a_i$. Ora, $a_n=A_{n}-A_{n-1}$...

(tra l'altro, se non mi sbaglio tra i vecchi esercizi del senior 2002 che vengono riproposti ogni anno negli stage senior ce n'è uno che si fa esattamente con lo stesso trucco...)

[exodd]

Non so come ti viene, ma a me risulta una successione tra gli $ A_i $ dipendente dai 3 termini precedenti.. la cui equazione associata non è scomponibile nei razionali..

[sasha™]

Anche a me viene una cosa simile... La cosa divertente è che, fissati i primi tre termini, il quarto viene diverso con le due formule.

[exodd]

Anche a me viene una cosa simile... La cosa divertente è che, fissati i primi tre termini, il quarto viene diverso con le due formule.

?????
Non so cosa vuoi dire..
Non ti viene

Testo nascosto:

$ A_n=3A_{n-1}+A_{n-2}-A_{n-3} $?

[sasha™]

Sì, mi viene quella. Ma con $a_1 = 2$, $a_2 = 7$ e $a_3 = 22$, con $a_n = a_{n-2} + 2\cdot\sum a_i$ ottengo $a_4 = 69$, con l'altra $a_4 = 71$... Avrò sbagliato i conti.

[exodd]

Devi porre anche $ a_0=1 $, altrimenti non viene..

[fph]

Non so come ti viene, ma a me risulta una successione tra gli $ A_i $ dipendente dai 3 termini precedenti.. la cui equazione associata non è scomponibile nei razionali..

Esatto -- una formula più semplice non può esserci. Pensavo che il punto fosse arrivare facilmente alla ricorrenza "corta" per gli $A_i$.

[Karl Zsigmondy]

Si, in effetti è così, solo che mi ero perso qualcosa tentando di generalizzare e mi veniva una formula. Scusate.

[sasha™]

Ma quindi non c'è modo di passare da quella ricorsiva ad una chiusa?

[fph]

C'è una formula chiusa, a cui si arriva con teoria standard delle ricorrenze lineari (la lezione A3 di un senior), ma coinvolge le tre radici irrazionali di un polinomio di terzo grado.

[sasha™]

Il procedimento è lo stesso per quello con le formule dipendenti da due termini precedenti?