Pietre preziose

[Cammy87]

1) Devo realizzare uno scettro incastonando in successione dall'alto verso il basso 18 pietre preziose scelte tra smeraldi verdi (V) e rubini rossi (R); non si possono mettere, però, due pietre verdi vicine. Quante possibili combinazioni posso avere?

Penso di avere trovato una soluzione, un po' lunga , ma non sono sicuro che sia giusta.

2) Se invece dovessi incastonare le pietre in una corona circolare, quante combinazioni ci sono?

[jim]

Il primo mi viene F_20 ,ossia Il 20° elemento dellla serie di Fibonacci. Si dimostra, in generale che per n gioielli, si hanno F_n+2 combinazioni. Aspetto a postare la soluzione che è abbastanza semplice (sempre ammesso che non abbia scritto io qualche fesseria).
Il secondo mi viene, in funzione di n, [F_(n+2)]-[F_(n-2)].

[Cammy87]

Potresti postare la tua dimostrazione jim, quando hai tempo?
Grazie.

[darkcrystal]

Intanto posto la mia...
Sia $ F_n $ l'n-esimo numero di Fibonacci.
Allora, chiamiamo $ R_n $ il numero di combinazioni con n posti a disposizione tali che l'ultimo posto sia occupato da un rubino, e $ V_n $ la stessa cosa ma quando all'ultimo posto c'è uno smeraldo.
Si vede facilmente che $ R_2=2, V_2=1 $.
Quando aggiungo un posto, da ogni combinazione che finiva con R ne formo 2 (aggiungendo R o V) e da ognuna che finiva con V ne formo 1 (aggiungendo R).
Si formano così delle nuove combinazioni, di cui $ R_n $ finiscono con un V, mentre $ V_n+R_n $ finiscono con un R.
Scrivendo le successioni
$ R_{n+1}=R_n+V_n $
$ V_{n+1}=R_n $ si arriva immediatamente a
$ R_{n+1}=R_n+R_{n-1} $
$ V_{n+1}=R_n $, dal che segue che
$ R_n=F_{n+1} $ e $ V_n=F_{n} $
Il numero di combinazioni totali con un determinato numero K di posti è dato da $ T_K=R_K+V_K=F_{k+1}+F_k=F_{k+2} $, c.v.d.

[darkcrystal]

Per la seconda parte... se n è pari mi viene $ \displaystyle 2^{\frac{n}{2}} $, mentre se è dispari $ \displaystyle 2^{\frac{n-1}{2}} $ ma non sono molto convinto...
Comunque: partiamo da una corona fatta tutta di pietre rosse.
Caso 1: n è pari.
Adesso è ovvio che posso cambiare una pietra ogni due con una verde, e rispettare lo stesso le ipotesi. Le pietre sottoposte a cambiamento sono quindi n/2 e ognuna può assumere due "stati" (R e V). Perciò le combinazioni sono $ \displaystyle 2^{\frac{n}{2}} $ (tutto ciò ovviamente sempre a meno di rotazioni, altrimenti non funziona!)

Caso 2: n è dispari.
Ci devono perciò essere due R vicine. Quelle che posso cambiare sono quindi solo $ \displaystyle \frac{n-1}{2} $, e si conclude come prima.

E' giusto?? Non mi sembra funzioni molto con quanto dice Jim... ma forse lui ha considerato combinazioni ruotate come diverse...

[jim]

@ Cammy87: Scusa, non ho visto il post che avevi messo, comunque, per l'1 il trucco è quello di vedere un po' come "funziona" con l'albero delle combinazioni, e poi dimostrare per induzione, come ha fatto darkcrystal.
@ darkcrystal: il 2 l'ho fatto nello stesso modo dell'1, e forse è lì che ho sbagliato: cioè parto sempre con l'albero delle combinazioni: per esempio, se n è 5, viene

1 V________________R
2 R______________V____R
3 V___R__________R____V__R
4 R___V__R______V_R__R__V_R
5 R___R__R_____R_VR_VR__R_VR

In pratica è uguale, ma bisogna fare attenzione al ramo che parte da V, in modo che qualsiasi gemma della (n-1)-esima posizione (del ramo di V) ne generi comunque una rossa nella n-esima, in modo che attaccandosi alla prima, non vi siano due V consecutive. In questo modo si vede che il ramo che parte da R ne genera $ F_{n+1} $, mentre il ramo che parte da V ne genera $ F_{n-1} $.
Solo per chiarire il risultato che avevo dato nel primo post,
$ F_{n+1} + F_{n-1} = F_{n+2} - F_{n-2} $

Per quanto riguarda la tua soluzione del 2, se devo essere sincero non convince troppo neppure me... soprattutto quando dici:

Caso 1: n è pari.
Adesso è ovvio che posso cambiare una pietra ogni due con una verde, e rispettare lo stesso le ipotesi. Le pietre sottoposte a cambiamento sono quindi n/2 e ognuna può assumere due "stati" (R e V).

Ora secondo me il problema sta qui... anche se non so dirti esattamente dove sia; per fare un esempio, però, pensa a n=4. Secondo il tuo metodo i casi possibili dovrebbero essere 4 (senza contare le rotazioni), mentre invece sono solo 3:
RRRR, VRRR, VRVR (+ rotazioni, da leggersi "incollando" la prima e l'ultima lettera). Fammi poi sapere se scopri l'inghippo!
Buona notte
Edo

[darkcrystal]

Si è vero, l'errore consiste nel fatto che sono io che non considero le rotazioni (ad esempio è vero che posso mettere una sola pietra verde in n/2 posti, ma tutte queste combinazioni sono uguali a meno di rotazioni )
Grazie dell'osservazione, ciao!