Parole... palindrome

Giochini matematici elementari ma non olimpici.
Rispondi
bĕlcōlŏn
Messaggi: 145
Iscritto il: 22 gen 2011, 12:56

Parole... palindrome

Messaggio da bĕlcōlŏn » 19 mag 2011, 14:41

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)

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Re: Parole... palindrome

Messaggio da SkZ » 19 mag 2011, 20:02

intendi in pratica una serie stile fibonacci? ogni parola e' la "somma' delle 2 che precedono?
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

bĕlcōlŏn
Messaggi: 145
Iscritto il: 22 gen 2011, 12:56

Re: Parole... palindrome

Messaggio da bĕlcōlŏn » 19 mag 2011, 20:04

SkZ ha scritto:intendi in pratica una serie stile fibonacci? ogni parola e' la "somma' delle 2 che precedono?
a, b, ab, bab, ...
Esattamente.
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)

Avatar utente
balossino
Messaggi: 103
Iscritto il: 20 mag 2011, 19:38

Re: Parole... palindrome

Messaggio da balossino » 21 mag 2011, 19:42

Provo a rispondere io... siate clementi se non uso il latex, è il mio primo giorno :roll:

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.

bĕlcōlŏn
Messaggi: 145
Iscritto il: 22 gen 2011, 12:56

Re: Parole... palindrome

Messaggio da bĕlcōlŏn » 06 giu 2011, 13:26

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.
Forse ho capito cosa intendi, ma non ne sono sicuro, potresti essere più chiaro? :)
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)

ileo83
Messaggi: 69
Iscritto il: 03 giu 2011, 23:44
Località: pisa

Re: Parole... palindrome

Messaggio da ileo83 » 06 giu 2011, 15:57

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

Avatar utente
Drago96
Messaggi: 1145
Iscritto il: 14 mar 2011, 16:57
Località: Provincia di Torino
Contatta:

Re: Parole... palindrome

Messaggio da Drago96 » 06 giu 2011, 16:03

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!
$a=A_0$ Invece il problema dice "accostando le parole $A_1A_2...A_n$" ;)
Imagination is more important than knowledge. For knowledge is limited, whereas imagination embraces the entire world, stimulating progress, giving birth to evolution (A. Einstein)

Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: Parole... palindrome

Messaggio da kalu » 07 giu 2011, 12:56

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.
Pota gnari!

bĕlcōlŏn
Messaggi: 145
Iscritto il: 22 gen 2011, 12:56

Re: Parole... palindrome

Messaggio da bĕlcōlŏn » 07 giu 2011, 18:19

Perfetto kalu, è identica alla mia :)
"Il bon ton è la grazia del saper vivere, la leggerezza dell' esistere." (Lina Sotis, perfidamente elegante)

Avatar utente
kalu
Messaggi: 297
Iscritto il: 23 nov 2010, 16:52
Località: Pisa

Re: Parole... palindrome

Messaggio da kalu » 07 giu 2011, 18:33

oh bene belcolon (perdonami le quantità), per me è un onore scrivere dimostrazioni identiche alle tue :D
Pota gnari!

Rispondi