O problema frumoasa

[zec]

 Aceasta problema a fost propusa la o olimpiada internationala.
Un alfabet are 3 litere.Cu el se pot forma diferite cuvinte.Unele siruri de litere,fiecare format din cel putin doua litere sunt interzise.Doua siruri interzise diferite au intodeauna lungimi diferite.
 Sa se demonstreze ca se pot forma cuvinte oricat de lungi ce nu contin siruri interzise de litere.

P.S. demonstratia o voi da ,dar intai as vrea sa vad si opinii, idei ,de ce nu poate o demonstratie completa de la alti participanti pe forum pana voi arata cum se face.
Am decis sa fac aceasta propunere si din faptul ca in ultimul timp forumul a fost privat de acest gen de subiecte.

[meteor]

Doua siruri interzise diferite au intodeauna lungimi diferite.

Nu inteleg conditia aceasta, daca doresti detaliaz-o.

[Etcetera]

Daca nu luam in calcul sirul de n litere, in care una din litere se repeta consecutiv ( de exemplu : abccabc), atunci sirurile vor fi :

ab, ac
ba, bc
ca, cb
sirurile formate din doua litere ;

aba, abc, aca, acb
bab, bac, bca, bcb
cac, cab, cba, cbc,
sirurile formate din trei litere ;

etcetera.

Continuand, rezulta ca pentru un sir de n litere in care aceeasi litera nu se repeta consecutiv, sunt siruri diferite de n litere.

Din acest numar de combinatii cel mult unul poate contine un sir care este interzis, pentru ca doua siruri interzise diferite nu au aceeasi lungime.
Din pot fi in incluse in constructia sirului si (sub)siruri care sunt interzise.

Daca sirul interzis de n litere nu contine in alcatuirea lui un sir de n-m litere interzis, atunci sunt cel putin (2n+1) siruri de n litere care nu sunt interzise.
n,m naturale.

Asta imi reiese din calcule, desi nu este o demonstratie propriu-zisa, dar am vreo doua ore de cand tot fac combinatii  si sunt sigur ca demonstratia trebuie sa fie mai simpla si nu necesita atata analiza.

[zec]

 Pot aparea litere identice una dupa alta,problema nu precizeaza cum arata sirurile interzise dar ne zice ca au cel putin 2 litere lungime si daca exista in cel mai rau caz pentru orice lungime n atunci acel sir este singurul de aceasta lungime.
  Deci pentru etcetera ,ai facut bine acolo dar tine cont de faptul ca unele siruri sunt interzise ceea ce ne face sa stim ca exista aceste siruri dar nu stim exact cum arata si nici nu trebuie sa  le aflam.
 Ca sa intelegeti mai bine problema la un cuvant de 10 litere poate aparea o secventa interzisa de 2,3,...9 sau chiar 10 litere in acel cuvant.Faptul ca in enunt au precizat ca e un sir, asta semnifica ca nu putem lua decat litere consecutive in acele secvente ,ca in ideea cum ai considerat tu in acel exemplu ,ca avand un sir interzis de 2 litere.
 Ceea ce trebuie aratat este ca exista pentru orice n un cuvant de n litere in care nu avem sir interzis.Am putea numi aceste cuvinte ca cuvinte corecte.
 Ideea demonstratiei ar fi :Daca consideram cu An numarul cuvintelor corecte de lungime n sa aratati ca An>0 oricare ar fi n.

[mircea_p]

Eu m-am gandit mai degraba la un algoritm. Dandu-se un cavant de n litere, cum sa-l curatam de sirurile interzise. Daca aratam ca exista un astfel de algoritm, am putea considera ca am demonstrat, nu?

Ma gandeam sa luam cel mai lung sir interzis si sa-l inlocuim cu unul bun (stim ca exista, orice alt sir de aceeasi lungime e bun).
Apoi luam urmatorul sir interzis (noi siruri interzise pot rezulta dupa fiecare inlocuire).
Cred ca ar merge pentru un program pe computer.

[Etcetera]

Consideram cele 3 litere ale alfabetului literele a, b, c.
Pentru ca un sir interzis contine cel putin 2 litere, inseamna ca niciunul din sirurile formate dintr-o litera nu sunt interzise.
Problema pleaca de aici combinand toate aceste trei litere.
Prin combinatia acestor litere se pot obtine mai multe siruri de 2 litere, din care doar unul singur este interzis, pentru ca doua siruri interzise au lungimi diferite.
Daca ab este sirul de 2 litere interzis, atunci orice sir de 3 litere care nu contine in alcatuirea lui sirul ab este un sir corect de 3 litere, care nu este interzis (spre exemplu aac, acb, bbb etc)
Din acestea de 3 litere care nu contin sirul ab, exista un singur sir de 3 litere care este interzis. Sa spunem, sirul acc.
Sa vedem daca exista un sir de 4 litere care sa nu contina un sir interzis de 2 litere (ab) sau un sir interzis de 3 litere (acc). Dar avem nevoie de cel putin doua siruri, pentru ca unul dintre ele poate fi considerat sirul de 4 litere interzis.
acac, acbb, bcac, cacb etc
Se pare ca sunt.
Ma gandesc ca rationamentul ar trebui continuat in acest fel.

Adica, daca exista cel putin un sir de n litere care nu este interzis, atunci exista cel putin un sir de n+1 litere care nu este interzis.

Intr-adevar, problema este frumoasa.
Te stimuleaza sa dezvolti un rationament logic din care sa rezulte concluzia.
Este totusi o problema cu dificultate ridicata.

Sa incercam totusi.
Daca sirul de 2 litere interzis este aa, atunci sirul de 2 litere ab nu este interzis.
Cu sirul interzis ab se pot construi cel putin doua siruri de 3 litere :
aba, abb,.
Daca sirul de 3 litere interzis este aba, atunci cu sirul abb se pot  forma alte doua siruri de 4 litere :
abba,abbc ;
Daca sirul de 4 litere interzis este abba, atunci cu celelalt se poate forma un sir de 5 litere :
abbca, abbcb ;
Daca sirul de 5 litere interzis este abbca, atunci cu sirul de litere abbcb se pot forma alte doua siruri de 6 litere :
abbcba,abbcbb ;
Etcetera.

Si am putea sa stabilim ca daca exista cel putin un sir care nu este interzis de n litere, atunci exista cel putin un sir care nu este interzis de n+1 litere.

Chiar daca nu este complet, ma gandesc ca poate da idei si altora.

[zec]

@mircea
Daca il cureti de sirurile interzise nu mai ai de unde sa sti ce lungime ramane si devine cam greu de aratat ce se cere.
@etcetera
Esti destul de aproape de ideea problemei,totusi ideea demonstratiei se bazeaza pe lucrul cu siruri si in a gasi relatii intre An si An+1.Dupa care prin inductie de a demonstra o inegalitate care sa duca la An>0 ca fiind adevarat.Partea frumoasa a acestei probleme rezidua in idee de intelegere a textului si gasirea unui mod de constructie ,doar ca nu vom obtine o relatie de recurenta ci doar inegalitate si daca la prima vedere pare ca ar functiona ,din pacate ea nu ne demonstreaza afirmatia si trebuie sa incercam a crea noi o relatie care sa fie valabila si sa o demonstram.
 Mai pe rezumat problema nu prea da optiuni de a rezolva in multe alte moduri si calea spre rezolvare devine din ce in ce mai subtire si cam unica in ideea sa.

[mircea_p]

@mircea
Daca il cureti de sirurile interzise nu mai ai de unde sa sti ce lungime ramane si devine cam greu de aratat ce se cere.

Nu inteleg asta. Daca inlocuiesc un sir cu un altul de aceeasi lungime, de ce nu stiu ce lungime ramane? Nu ramane lungimea neschimbata dupa fiecare pas?

Stiu, nu e o demonstratie matematica, nici nu am zis asta.
Un matematician nu rezolva probleme, se multumeste sa arate ca exista solutii. Un fizician presupune ca exista solutii (pe baza principiului "natura mama nu e parsiva") si incerca sa le gasesca

[zec]

 Da ai dreptate dar ramane sa arati ca lungimea sirurilor interzise de lungime maxima scade la fiecare inlocuire.Lucru care se pare ca nu poate avea loc intodeauna.Si astefl in felul asta intri in impas din cauza ca nu sti unde inlocuiesti si risti sa formezi alt sir interzis de lungime mai mare.

[Etcetera]

Salut Zec !
Vreau sa te rog sa nu scrii inca demonstratia ta, pentru ca vreau sa mai analizez aceasta problema in mai multe moduri, iar daca o scrii nu ma mai ajuta propriu-zis.
Acum sunt prins tare cu altele si nu am asa de mult timp liber, dar o am mereu in vedere.
Ma gandeam la un moment dat ca ar putea fi o legatura intre aceasta problema si principiul primalitatii numerelor.
La fel de bine, un sir de n litere, este alcatuit din 2 siruri de n-1 litere, 3 siruri din n-2 litere, 4 siruri de n-3 litere etc.

Iar referitor la primalitate, spre exemplu, un sir de 6 litere este alcatuit, fie din 3 siruri de 2 litere, fie din 2 siruri de 3 litere, iar in functie de divizorii lui n ca numar de litere al sirului, el poate fi alcatuit dintr-un numar de siruri cu un numar prim de litere.
Si vreau sa vad daca este suficient sa se arate ca pentru orice n prim ca numar de litere al sirului, exista un sir care nu este interzis.
Sar putea sa nu aiba nicio legatura, dar vreau sa ma asigur ca intr-adevar nu exista nicio legatura, plecand de la conditiile problemei.

Tu ce parere ai, pierd timpul analizand asa ?
Ca eu am o problema cu numerele astea prime si am tendinta sa le iau ca si modalitate de analiza in aproape orice.

[zec]

Iti dau o indicatie.Daca ai un cuvant corect si adaugi o litera ,sirul interzis nu poate fi decat un sir de la sfarsitul cuvantului care poate avea o lungime k.Daca An e numarul sirurilor corecte de lungime n atunci daca adaugi o litera se formeaza 3An cuvinte care au lungimea n+1 din care poti elimina un anumit numar maxim de cuvinte care contin siruri interzise.Dar plecand pe acest rationament si calculand in acest fel ,pentru n foarte mare sirul astfel calculat tinde catre 0 si astfel ramanem blocati.De aceea e de cautat o alta inegalitate pe care sa o aratam prin inductie si sa demonstreze ca An>0 oricare ar fi n.
P.S de specificat faptul ca se adauga la sfarsitul cuvantului o litera.

[Etcetera]

Zec,
cred ca se si poate calcula numarul exact de siruri care nu sunt interzise de n litere, cu conditia ca orice sir interzis sa nu contina in alcatuirea lui un alt sir interzis.
Explicatia ar fi foarte lunga si obositoare si ezit sa o scriu acum ca sa nu postez un mesaj foarte lung. Daca o sa reusesc sa-l reduc la o logica mai simpla il postez.
Insa scriu asta pentru ca am nevoie sa ma ajuti sa stabilesc formula care "genereaza" numerele de mai jos in ordine consecutiva.
Cu alte cuvinte, numerele de mai jos sunt primii termeni ai sirului.
Putem generaliza o formula care sa le "genereze" ?

1
3 + 2
9 + 2 + 2*(3+2)
27  +    2*(3+2) + 2*[9+2+2(3+2)]
81           +          2*[9+2+2(3+2)]   +   2*{27 + 2*(3+2) + 2*[9+2+2(3+2)]}
.................
Le-am scris mai despartit ca sa poti observa mai usor cum se construieste celalalt termen.
Exista totusi o modalitate de a calcula efectiv daca un sir de n litere poate fi alcatuit din siruri care nu sunt interzise, deci care este un sir corect.
Iar termenii de mai sus, apar ca tipar in numarul de siruri de o lungime mai mica, care trebuiesc eliminati ( si pot fi eliminati) dintr-un sir de n litere.

Daca reusim sa gasim o formula generalizatoare pentru termenii de mai sus, pot sa stabilesc si prin calcul daca este sau nu adevarata concluzia problemei.

Oricum, unei probleme asa frumoase i s-ar cuveni o demonstratie la fel de frumoasa si nu atata calcul, dar eu vad mai repede constantele decat rationamentele logice.

[mircea_p]

Zec,
cred ca se si poate calcula numarul exact de siruri care nu sunt interzise de n litere, cu conditia ca orice sir interzis sa nu contina in alcatuirea lui un alt sir interzis.

Vrei sa spui ca un sir de lungime n care contine un sir interzis (mai scurt) este considerat interzis? Eu am inteles ca pentru fiecare lungime n exista un singur sir interzis. Daca ar fi cum spui, are exista mult mai multe siruri interzise de lungime n, nu?

[Etcetera]

Pai din concluzia problemei reiese si ca :
" Sa se demonstreze ca se pot forma cuvinte oricat de lungi ce nu contin siruri interzise de litere."

Eu inteleg prin asta ca acel sir care contine un sir interzis, nu este un sir corect, nu neaparat interzis. De lungime n exista doar un singur sir interzis, dar pot fi siruri de lungime n care nu sunt interzise, insa pot contine siruri interzise si nu este un sir corect.
Eu asa inteleg problema.
Sa ne confirme, totusi, zec daca este corect asa.
Dar dificultatea problemei apare doar daca este analizata asa, altfel se simplifica situatia.

Oricum, eu am reusit sa izolez un tipar prin care se poate anula dintr-un sir de lungime n, sirurile de lungime mai mica. Tiparul este prezentat in mesajul anterior.
Daca spre exemplu, termenii de mai sus i-am denumi T(1), T(2), T(3),...,T(n)
,atunci numarul de siruri interzise mai mici care trebuie anulate din sirurile de lungime n sunt:
T(1)+T(2)+T(3)+...+T(n-2).
Deci mi-ar trebui trebui o relatie de recurenta pentru termenii din mesajul anterior.
Sper ca se intelege modul de "constructie" al termenilor.

O sa revin si cu un mesaj prin care sa explic de ce este asa, dar mesajul va fi lung si poate "plictisi" cititorul.

[zec]

Zec,
cred ca se si poate calcula numarul exact de siruri care nu sunt interzise de n litere, cu conditia ca orice sir interzis sa nu contina in alcatuirea lui un alt sir interzis.

Vrei sa spui ca un sir de lungime n care contine un sir interzis (mai scurt) este considerat interzis? Eu am inteles ca pentru fiecare lungime n exista un singur sir interzis. Daca ar fi cum spui, are exista mult mai multe siruri interzise de lungime n, nu?

DA