OliForum Matematico

Il problema è tratto dagli esercizi proposti da matematik.
Stavo provando l'ultimo che riporto:
In quanti modi posso mettere in fila i numeri da 1 a 10 in modo che vengano rispettate le seguenti regole:
a) il primo numero della fila è sempre "1",
b) la differenza tra due numeri che occupano posizioni consecutive nella fila non è mai superiore al più 2.

Nella soluzione è riportata la ricorsione che porta al risultato, io invece ottengo un sistema di ricorrenze che non riesco a semplificare.

EDIT: cambiato 16->14 nel titolo --fph

Ci fai vedere la tua soluzione? Senza è difficile capire dove ti sei bloccato!

Io più che altro ho provato a costruire una legge valide per stringhe lunghe n, non solo 10.
Quando provo a scrivere la successione per ricorrenza mi viene che se il primo numero è 1, allora sarà 1 o 10. Adesso in ciascun caso ho due modi di continuare, nello specifico ad 1 posso far succedere 2 o 3, al 10 faccio seguire o 9 o 8. Per simmetria so che le stringhe che cominciano per 10 sono uguali in numero a quelle che cominciano per 1, analogo ragionamento per le stringhe che cominciano con 9 e 2, quelle che cominciano per 8 e 3 e così via...
Quindi se chiamo $ x_n $ le stringhe che cominciano con il numero 1, allora ho che se cominciano con 1 le stringhe sono $ \frac{x_n}{2} $, se cominciano con 10 sono $ \frac{x_n}{2} $, se cominciano per 9 o 2 saranno $ \frac{y_n}{2} $, per 8 o 3 saranno $ \frac{z_n}{2} $.
Per quanto detto ho $ x_n=y_{n-1}+z{n-1} $, ma pur andando indietro con i pedici, cioè considerando anche gli $ n-2 $, ho che il sistema si ingrandisce dovendo considerare anche le stringhe che cominciano per 3 e 7 e non riesco a semplificare nulla.

Effettivamente così non funziona, per il motivo che hai visto tu. Prima piccola osservazione: secondo me il testo vuol dire "il primo numero è 1", non "il primo numero è 1 o 10", altrimenti avrebbe parlato di *cifre*. Ma qui cambia poco; come noti tu è solo un dividere per due. Seconda: quello che ti manca è capire un attimo qual è la regolarità del problema che puoi sfruttare. Cercando di risolvere il problema per $n=10$, come puoi riutilizzare quello per $n=9$ (e magari anche $n=8$)? Se metti le variabili come fai tu, il problema esplode e non riesci a riutilizzare nessuna delle variabili già scelte con un indice minore...

fph ha scritto: secondo me il testo vuol dire "il primo numero è 1", non "il primo numero è 1 o 10"...

Confermo.

Inoltre andrebbe leggermente cambiato il titolo: si tratta del problema 14 della lista, non del 16.

Hawk ha scritto:... Adesso in ciascun caso ho due modi di continuare, nello specifico ad 1 posso far succedere 2 o 3...

Piccolo suggerimento non invasivo: