Forumul Scientia

Matematică şi Logică => Matematică - probleme generale => Subiect creat de: zec din Noiembrie 24, 2012, 02:33:58 AM

Titlu: O problema frumoasa
Scris de: zec din Noiembrie 24, 2012, 02:33:58 AM
 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.
Titlu: Răspuns: O problema frumoasa
Scris de: meteor din Noiembrie 24, 2012, 09:23:52 PM
Citat din: zec din Noiembrie 24, 2012, 02:33:58 AM
Doua siruri interzise diferite au intodeauna lungimi diferite.
Nu inteleg conditia aceasta, daca doresti detaliaz-o.
Titlu: Răspuns: O problema frumoasa
Scris de: Etcetera din Noiembrie 24, 2012, 10:35:09 PM
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 [tex]3\cdot2^{n-1}[/tex] 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 [tex]3\cdot2^{n-1}-1[/tex] 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.


Titlu: Răspuns: O problema frumoasa
Scris de: zec din Noiembrie 25, 2012, 12:38:42 AM
 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.
Titlu: Răspuns: O problema frumoasa
Scris de: mircea_p din Noiembrie 25, 2012, 01:05:27 AM
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.

Titlu: Răspuns: O problema frumoasa
Scris de: Etcetera din Noiembrie 25, 2012, 09:54:16 AM
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.
Titlu: Răspuns: O problema frumoasa
Scris de: zec din Noiembrie 25, 2012, 06:43:35 PM
@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.
Titlu: Răspuns: O problema frumoasa
Scris de: mircea_p din Noiembrie 25, 2012, 08:24:03 PM
Citat din: zec din Noiembrie 25, 2012, 06:43:35 PM
@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 ;)
Titlu: Răspuns: O problema frumoasa
Scris de: zec din Noiembrie 25, 2012, 11:19:14 PM
 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.
Titlu: Răspuns: O problema frumoasa
Scris de: Etcetera din Noiembrie 28, 2012, 09:01:58 AM
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.
Titlu: Răspuns: O problema frumoasa
Scris de: zec din Noiembrie 28, 2012, 09:45:43 AM
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.
Titlu: Răspuns: O problema frumoasa
Scris de: Etcetera din Noiembrie 28, 2012, 11:43:10 PM
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.
Titlu: Răspuns: O problema frumoasa
Scris de: mircea_p din Noiembrie 29, 2012, 12:01:17 AM
Citat din: Etcetera din Noiembrie 28, 2012, 11:43:10 PM
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?

Titlu: Răspuns: O problema frumoasa
Scris de: Etcetera din Noiembrie 29, 2012, 08:31:14 AM
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.
Titlu: Răspuns: O problema frumoasa
Scris de: zec din Noiembrie 29, 2012, 12:06:01 PM
Citat din: mircea_p din Noiembrie 29, 2012, 12:01:17 AM
Citat din: Etcetera din Noiembrie 28, 2012, 11:43:10 PM
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
Titlu: Răspuns: O problema frumoasa
Scris de: zec din Noiembrie 29, 2012, 12:26:00 PM
@etcetera Legat de confirmare intradevar asa e.
Despre termeni aceia nu m-am dumirit ce reprezinta T(n).Daca ar fi numarul de cuvinte corecte de lungime n atunci ai avea:
T(1)=3(toate cuvintele de lungime 1 sunt corecte din ipoteza)
T(2)=3x3-1=8 (din 9 cuvinte de 2 litere posibile doar 1 e interzis pe care il scadem)
T(3)=3x8-4=20(in cuvintele de 3 litere nu vom forma cuvinte cu sirul interzis de 2 litere si putem forma doar cu cuvintele corecte de 2 litere de aceea am 3x8 cuvinte posibile din care scad sirul interzis de 3 plus cele 3 siruri de lungime 2 interzis care se formeaza).
Dar in acest fel ne dam seama de felul cum se calculeaza,dar nu si demonstram ca T(n) e pozitiv pentru orice n.Sper sa intelegi mai bine problema de aici ,pentru ca vad ca deja ai inteles problema destul de bine si ai ajuns destul de departe.
Titlu: Răspuns: O problema frumoasa
Scris de: Etcetera din Noiembrie 29, 2012, 10:10:01 PM
Deocamdata nu stiu exact daca chiar nu putem ajunge la vreun rezultat si prin calcul propriu-zis. Personal as raspunde afirmativ pentru moment.
Oricum, sunt sigur ca tu ai o demonstratie eleganta si ca problema se poate demonstra prin inductie si nu neaparat prin calcul, dar m-am incins un pic cu aceste calcule si parca nu le pot lasa.
Plecand de la problema ta am dat peste altceva, prin calcul, care mi-a starnit interesul.
Cred totusi ca pot vorbi de acuratete maxima, de precizie 100%, si prin calculele mele.
Si sa-ti explic mai exact ce inseamna acesti termeni.

Pentru inceput, plecam de la conditia ca un sir de n litere interzis nu contine in alcatuirea lui niciun alt sir mai mic interzis .
Aceasta este de fapt situatia pentru care dintr-un numar maxim de combinatii de n litere (adica [tex]3^{n}[/tex] combinatii) exista cat mai multe combinatii care nu sunt corecte, avand in alcatuirea lor cel putin un sir interzis mai mic.

Daca notam cu [tex]A_{n][/tex] numarul de combinatii de n litere care sunt corecte, adica nu sunt siruri interzise sau au in corpul lor siruri interzise, atunci

[tex]A_{n}=3^{n}-(T_{n}+T_{n-1}+T_{n-2}+...+T_{3}+T_{2})[/tex]

Pentru suma aceasta de termeni de mai sus relatia de recurenta este :
daca     [tex]T_{n} = (3^{a} + b) +c[/tex],
atunci [tex]T_{n+1}= 3^{a+1} +c + 2T_{n}[/tex]

Primii termeni ai sirului sunt :
[tex](T_{1}=0)[/tex]
[tex]T_{2}=1[/tex]
[tex]T_{3}=3+2[/tex]
[tex]T_{4}=9+2+ 2\cdot(3+2)[/tex]
[tex]T_{5}=27+2\cdot(3+2)+2\cdot[9+2+2\cdot(3+2)][/tex]
........

Ca sa intelegi mai bine, numarul de combinatii maxime de 3 litere care contine un sir interzis de 2 litere este [tex]T_{3}[/tex], pentru un sir de 4 litere este [tex]T_{4}[/tex], pentru un sir de 5 litere este [tex]T_{5}[/tex] etc.

Numarul de combinatii de 7 litere, spre exemplu,
care contine un sir de 2 litere interzis este [tex]T_{7}[/tex],
care contine un sir de 3 litere interzis este [tex]T_{6}[/tex],
care contine un sir de 4 litere interzis este [tex]T_{5}[/tex],
care contine un sir de 5 litere interzis este [tex]T_{4}[/tex],
care contine un sir de 6 litere interzis este [tex]T_{3}[/tex],
care contine un sir de 7 litere interzis este [tex]T_{2}[/tex]

Daca numarul maxim de combinatii de 7 litere este [tex]3^{7}[/tex], atunci numarul de combinatii de 7 litere care nu sunt interzise este :

[tex]A_{7}=3^{7}-(T_{7}+T_{6}+T_{5}+T_{4}+T_{3}+T_{2})[/tex]

"Cu precizie matematica !" , as spune.

Problema mea in aceasta situatie, este sa pot reduce termenul general n, [tex]T_{n}[/tex],
la o formula ce permite compararea cu o putere de trei, sa pot stabili daca aceea diferenta este mai mare ca zero intotdeauna, pentru orice n.

Asa, intuitiv in functie de cum am calculat si am vazut ca valorile cresc, as raspunde afirmativ.
Titlu: Răspuns: O problema frumoasa
Scris de: Etcetera din Noiembrie 30, 2012, 01:12:42 PM
Sau, tot prin calcule, am putea arata si asa :

Daca un sir de lungime n este interzis, atunci sunt cel mult [tex](m-1)(3^{m-2})[/tex] siruri de lungime m care contin in corpul lor un sir de lungime n interzis.

Daca notam cu (X) sirul de lungime n interzis,
atunci
pentru un sir de lungime n+1, sunt 6 siruri care contin in alcatuirea lor un sir interzis de n litere :
a(X), b(X), c(X)
(X)a, (X)b, (X)c ;
pentru un sir de lungime n+2, sunt 27 siruri care contin in alcatuirea lor un sir interzis de n litere :
aa(X), ab(X), ac(X)  
ba(X), bb(X), bc(X)
ca(X), cb(X), cc(X)

a(X)a, a(X)b, a(X)c
b(X)a, b(X)b, b(X)c
c(X)a, c(X)b, c(X)c

(X)aa, (X)ab, (X)ac
(X)ba, (X)bb, (X)bc
(X)ca, (X)cb, (X)cc

etcetera.
Din aceste numar de siruri mai trebuie eliminat/e anumite combinatii pentru ca apar de doua ori; spre exemplu, daca aa este sirul X interzis de 2 litere, atunci aa(X) este un sir identic cu (X)aa.
Dar oricum, daca vom calculam dupa formula [tex](m-1)(3^{m-2})[/tex], atunci putem sa spunem ca numarul minim de siruri de lungime n care sunt corecte este egal cu:

[tex]3^n-[(n-1)\cdot 3^{n-2}+(n-2)\cdot 3^{n-3}+(n-3)\cdot 3^{n-4}+...+2\cdot 3^{1}+1][/tex]

Este diferenta aceasta mai mare ca zero ?
Titlu: Răspuns: O problema frumoasa
Scris de: zec din Decembrie 02, 2012, 12:53:34 AM
Ultima postare te ai cam departat de rezolvare.
Ok acuma am sa prezint demonstratia.
Sa notam cu An numarul cuvintelor corecte de lungime n.
Cuvintele de lungime An+1  se pot forma  prin adaugarea unei litere la sfarsitul unui cuvant corect de lungime n.Este evident ca daca avem un cuvant corect de n+1 litere si ii elimin ultima litera ramane un cuvant de n litere corect.
Deci daca adaug totusi o litera la sfarsitul unui cuvant de n litere pot obtine 3 cuvinte de n+1 litere care pot avea siruri interzise dar numai la sfarsitul sau.Lungimea sirului interzis poate fi k=2,3....,n+1 litere si daca exista acest sir e cel mult 1.Astfel obtinem urmatoarea relatie:
[tex]A_{n+1}\ge 3A_n-A_{n-1}-\cdots -A_1-1[/tex].
Aceasta inegalitate ca sa fie inteleasa zice urmatorarele :
-An+1 are cel putin 3An din care scadem cuvinte cu siruri interzise de lungime n+1,n,...,2
-Numarul cuvintelor de lungime n+1 care contine la sfarsit un sir de lungime k interzis este egal cu numarul cuvintelor corecte de lungime n+1-k
.Nu pare posibil a arata direct ca An>0 prin inductie cu aceasta relatie si de aceea ar trebui incercata alta relatie care sa o implice.
Cel mai simplu ar fi de aratat [tex]A_n\ge A_{n-1}+\cdots+A_1+1[/tex].Pe care o demonstram prin inductie.
Pentru n=1 se verifica imediat tinand cont ca A1=3 lucru care reiese din ipoteza.
Presupanand pentru n adevarat sa aratam ptr n+1
[tex]A_{n+1}\ge A_n+2A_n-(A_{n-1}+\cdots+A_1+1)\ge A_n+(A_{n-1}+\cdots+A_1+1)[/tex]
Astfel demonstratia sa incheiat caci ultima inegalitate ne arata ca An>0.
Cateva observatii merita de apreciat.daca nu am fi tinut cont ca primele n+1-k ale fiecaruia din cuvintele formate e un cuvant corect atunci am fi obtinut o alta relatie:
[tex]A_{n+1}\ge A_n-3^{n-1}-\cdots-3-1[/tex] care nu ar fi rezolvat problema.
Partea frumoasa a problemei se vede in demonstratie.Se vede ca suntem intro mare masura limitati in a determina o relatie despre An de aceea felul in care se construiesc cuvintele corecte ar parea ideea demonstratiei.Dupa ce remarcam cum se formeaza un cuvant corect apare problema  legata de numararea lor.(Aici  te ai pierdut tu).Si partea incredibila e ca nu putem demonstra direct prin inductie  ca An>0 cu relatia initiala.
Titlu: Răspuns: O problema frumoasa
Scris de: Etcetera din Decembrie 03, 2012, 01:49:41 PM
Salut zec !
Nu inteleg exact tot rationamentul si mi-e un pic dificil sa-l urmaresc.

La partea cu sfarsitul sirurilor am o mica obiectie, pe care mi-as dori sa mi-o elimini.

Intr-adevar, daca la un cuvant de n litere corect adaugam o litera, atunci se obtine un sir de n+1 litere care poate avea la sfarsit un sir mai mic interzis.
Insa daca analizam altfel nu prea rezulta si aici fie ma incurc un pic si nu pierd sirul logic al implicatiilor, fie chiar nu rezulta.

Adaugand o litera la un oarecare sir de litere, inseamna ca sunt trei combinatii de doua litere ce pot fi formate la sfarsitul sirului.
Putem pleca de la ipoteza ca una din aceste trei combinatii poate fi un sir de 2 litere interzis ?
Daca da, mai raman doar doua combinatii.

Daca adaugand la sirul initial una din celelalte doua litere, putem pleca, la fel, la concluzia ca intr-una din combinatiile de 3 litere de la sfarsitul cuvantului una poate fi chiar cea interzisa.
Mai ramane una, care fie poate fi o combinatie interzisa de 4 litere, sau chiar sirul interzis de n+1 litere.
Mai departe nu prea putem merge, analizand sirurile de la sfarsit spre inceput.
Sau cel putin, asa cum ai mentionat si tu, nu fara sa analizezi si altceva in paralel.
Oricum, o sa incerc sa analizez mai bine ce ai scris, pentru ca s-ar putea sa-mi dau seama si ce si unde nu inteleg exact.
Titlu: Răspuns: O problema frumoasa
Scris de: zec din Decembrie 03, 2012, 06:01:42 PM
 Evident obtii 3 combinatii dintrun cuvant fixat.Greseala ta pare sa vina din faptul ca nu consideri toate cuvintele corecte.
Si intradevar adaugand o litera poti obtine o combinatie de 2 care poate fi ceea interzisa ceea ce la mine sa tradus in cuvant incorect si sa scazut din numarul cuvintelor corecte posibile.Numarul  cuvintelor care au de exemplu un sir de numai 2 litere interzise in coada este egal cu numarul cuvintelor corecte care ramane dupa ce stergi acel sir adica cu numarul cuvintelor de lungime n-1 (in cazul meu cu n+1) sau in caz particular la un exemplu cu 5 litere este egal cu numarul cuvintelor corecte de lungime 3.
Cuvintele corecte de lungime mai mare nu se pot forma decat din cuvinte corecte de lungime mai mica prin adaugarea unei litere sau al unui cuvant corect prin lipirea in fata, in spate sau in interiorul sau.Am ales la sfarsitul cuvantului sa adaug o litera caci altfel devenea complicat si eram cu multe neclaritati exact ca in rationamentul lui mircea(el avand o idee de acest gen).
Deci totul merge recursiv cuvintele de lungime 2 se formeaza din cele de lungime 1 ,cele de lungime 3 se formeaza din cele de lungime 2 etc.
Adica  cuvintele de lungime n+1 le formam din cele corecte de lungime n care la randul sau sau format din cele de lungime n-1,ceea ce explica de ce daca apare o secventa interzisa  o gasim in numarul de combinatii  egal cu numarul sirurilor corecte de aceea lungime ramasa din stergerea acelui sir interzis.