Matematică şi Logică > Matematică - probleme generale

O problema frumoasa

<< < (3/5) > >>

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:

--- Citat din: Etcetera din Noiembrie 28, 2012, 11:43:10 p.m. ---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.

--- Terminare citat ---
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:

--- Citat din: mircea_p din Noiembrie 29, 2012, 12:01:17 a.m. ---
--- Citat din: Etcetera din Noiembrie 28, 2012, 11:43:10 p.m. ---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.

--- Terminare citat ---
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?



--- Terminare citat ---
DA

Navigare

[0] Indexul de Mesaje

[#] Pagina următoare

[*] Pagina precedentă

Du-te la versiunea completă