Parole... palindrome
Parole... palindrome
Definisco una sequenza di parole $A$ in questo modo: $A_0=a$, $A_1=b$ e ogni parola $A_n$ con $n \geq 2$ si ottiene accostando $A_{n-2} A_{n-1}$. Dimostrare che per ogni $n\geq 1$ accostando le parole $A_1A_2...A_n$ se ne ottiene una palindroma.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Parole... palindrome
intendi in pratica una serie stile fibonacci? ogni parola e' la "somma' delle 2 che precedono?
a, b, ab, bab, ...
a, b, ab, bab, ...
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php
Re: Parole... palindrome
Esattamente.SkZ ha scritto:intendi in pratica una serie stile fibonacci? ogni parola e' la "somma' delle 2 che precedono?
a, b, ab, bab, ...
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Parole... palindrome
Provo a rispondere io... siate clementi se non uso il latex, è il mio primo giorno
Data una serie A(1)A(2)...A(n), definiamo una "mossa" come il passaggio alla serie successiva [cioè quella che termina con A(n+1)]. Si verifica banalmente che A(1)A(2) => bab è una serie palindroma. Cercheremo di dimostrare la proprietà richiesta per induzione. Ogni mossa può essere descritta come l'aggiunta del termine A(n+1). Esso appartiene alla coda della serie, perché è stato formato con gli ultimi due termini aggiunti nella mossa precedente. Ma allora, per simmetria (perché abbiamo detto che la serie è palindroma), possiamo considerare A(n+1) come la prima parte della serie precedente, specchiata. A questo punto, sempre per simmetria, avremo ottenuto una nuova serie palindroma.
Data una serie A(1)A(2)...A(n), definiamo una "mossa" come il passaggio alla serie successiva [cioè quella che termina con A(n+1)]. Si verifica banalmente che A(1)A(2) => bab è una serie palindroma. Cercheremo di dimostrare la proprietà richiesta per induzione. Ogni mossa può essere descritta come l'aggiunta del termine A(n+1). Esso appartiene alla coda della serie, perché è stato formato con gli ultimi due termini aggiunti nella mossa precedente. Ma allora, per simmetria (perché abbiamo detto che la serie è palindroma), possiamo considerare A(n+1) come la prima parte della serie precedente, specchiata. A questo punto, sempre per simmetria, avremo ottenuto una nuova serie palindroma.
Re: Parole... palindrome
Forse ho capito cosa intendi, ma non ne sono sicuro, potresti essere più chiaro?balossino ha scritto:Esso appartiene alla coda della serie, perché è stato formato con gli ultimi due termini aggiunti nella mossa precedente. Ma allora, per simmetria (perché abbiamo detto che la serie è palindroma), possiamo considerare A(n+1) come la prima parte della serie precedente, specchiata.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Parole... palindrome
scusate ma gia' al passo 2 la parola non e' palindroma. cioe' abab, che sarebbe a+b+ab, non e' mica palindroma deh!
Il vecchio conio OO
Re: Parole... palindrome
$a=A_0$ Invece il problema dice "accostando le parole $A_1A_2...A_n$"ileo83 ha scritto:scusate ma gia' al passo 2 la parola non e' palindroma. cioe' abab, che sarebbe a+b+ab, non e' mica palindroma deh!
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)
Re: Parole... palindrome
Per ogni intero positivo $ n $, chiamo $ K_n $ la parola ottenuta accostando $ A_1A_2...A_n $.
$ K_1=A_1=b $, ed è chiaramente pailndroma. Proverò a dimostrare che $ K_n $ è palindroma per ogni $ n>1 $.
Per ogni $ n>1 $, chiamo $ R_n $ (radice di $ A_n $) la parte iniziale di $ A_n $, costituita dalle sue prime due lettere; chiamo invece $ D_n $ (desinenza di $ A_n $) la parte finale di $ A_n $, che segue $ R_n $ (quindi $ A_n=R_nD_n $).
Dimostro per induzione che, per ogni intero positivo $ n $, $ R_{2n}=ab $ e $ R_{2n+1}=ba $. Noto che è così per $ n=1 $; supponendo che la proprietà si verificata per $ n $ osservo che $ A_{2n+2}=A_{2n}A_{2n+1} $ (e dunque $ R_{2n+2}=R_{2n} $), mentre $ A_{2n+3}=A_{2n+1}A_{2n+2} $ (e dunque $ R_{2n+3}=R_{2n+1} $).
Dimostro ora per induzione che $ D_n=K_{n-2} $ (qualora $ D_n $ esista). $ D_2 $ non esiste, mentre per $ n=3 $ e $ n=4 $ la proprietà è verificata. Suppongo che la proprietà sia verificata per $ n $ e per $ n-1 $ ($ n\ge4 $). Allora $ D_{n+1}=D_{n-1}+A_{n}=K_{n-3}A_{n-2}A_{n-1}=K_{n-1} $.
A questo punto dimostro la tesi per induzione. $ K_2 $, $ K_3 $ e $ K_4 $ sono palindrome. Suppongo che $ K_{n-1} $ e $ K_{n-2} $ siano palindrome ($ n\ge4 $). Allora $ K_{n+1}=K_{n-1}R_{n}D_{n}R_{n+1}D_{n+1}=K_{n-1}R_{n}K_{n-2}R_{n+1}K_{n-1} $. $ K_{n-1} $ e $ K_{n-2} $ sono palindrome per ipotesi induttiva, inoltre $ R_n $ e $ R_{n+1} $ sono speculari essendo rispettivamente $ ab $ e $ ba $ o viceversa: quindi $ K_{n+1} $ è palindroma.
$ K_1=A_1=b $, ed è chiaramente pailndroma. Proverò a dimostrare che $ K_n $ è palindroma per ogni $ n>1 $.
Per ogni $ n>1 $, chiamo $ R_n $ (radice di $ A_n $) la parte iniziale di $ A_n $, costituita dalle sue prime due lettere; chiamo invece $ D_n $ (desinenza di $ A_n $) la parte finale di $ A_n $, che segue $ R_n $ (quindi $ A_n=R_nD_n $).
Dimostro per induzione che, per ogni intero positivo $ n $, $ R_{2n}=ab $ e $ R_{2n+1}=ba $. Noto che è così per $ n=1 $; supponendo che la proprietà si verificata per $ n $ osservo che $ A_{2n+2}=A_{2n}A_{2n+1} $ (e dunque $ R_{2n+2}=R_{2n} $), mentre $ A_{2n+3}=A_{2n+1}A_{2n+2} $ (e dunque $ R_{2n+3}=R_{2n+1} $).
Dimostro ora per induzione che $ D_n=K_{n-2} $ (qualora $ D_n $ esista). $ D_2 $ non esiste, mentre per $ n=3 $ e $ n=4 $ la proprietà è verificata. Suppongo che la proprietà sia verificata per $ n $ e per $ n-1 $ ($ n\ge4 $). Allora $ D_{n+1}=D_{n-1}+A_{n}=K_{n-3}A_{n-2}A_{n-1}=K_{n-1} $.
A questo punto dimostro la tesi per induzione. $ K_2 $, $ K_3 $ e $ K_4 $ sono palindrome. Suppongo che $ K_{n-1} $ e $ K_{n-2} $ siano palindrome ($ n\ge4 $). Allora $ K_{n+1}=K_{n-1}R_{n}D_{n}R_{n+1}D_{n+1}=K_{n-1}R_{n}K_{n-2}R_{n+1}K_{n-1} $. $ K_{n-1} $ e $ K_{n-2} $ sono palindrome per ipotesi induttiva, inoltre $ R_n $ e $ R_{n+1} $ sono speculari essendo rispettivamente $ ab $ e $ ba $ o viceversa: quindi $ K_{n+1} $ è palindroma.
Pota gnari!
Re: Parole... palindrome
Perfetto kalu, è identica alla mia
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)
Re: Parole... palindrome
oh bene belcolon (perdonami le quantità), per me è un onore scrivere dimostrazioni identiche alle tue
Pota gnari!