Problema 14 di combinatoria ricorsiva

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Problema 14 di combinatoria ricorsiva

Messaggio da Hawk »

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
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Problema 16 di combinatoria ricorsiva

Messaggio da fph »

Ci fai vedere la tua soluzione? Senza è difficile capire dove ti sei bloccato!
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: Problema 16 di combinatoria ricorsiva

Messaggio da Hawk »

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.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »
fph
Site Admin
Messaggi: 3956
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Problema 16 di combinatoria ricorsiva

Messaggio da fph »

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...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]
matematik
Messaggi: 85
Iscritto il: 27 apr 2009, 11:42
Località: Roma

Re: Problema 16 di combinatoria ricorsiva

Messaggio da matematik »

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. :D
matematik
Messaggi: 85
Iscritto il: 27 apr 2009, 11:42
Località: Roma

Re: Problema 16 di combinatoria ricorsiva

Messaggio da matematik »

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:
Testo nascosto:
Secondo me si arriva meglio alla legge ricorsiva, non chiedendosi chi va vicino all'1, ma chiedendosi dove si può piazzare il 2.
Rispondi