Autor Subiect: O problema frumoasa (Citit de 23246 ori)

zec · « **Răspuns #15 :** Noiembrie 29, 2012, 12:26:00 p.m. »

@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.

Etcetera · « **Răspuns #16 :** Noiembrie 29, 2012, 10:10:01 p.m. »

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 $3^{n}$ combinatii) exista cat mai multe combinatii care nu sunt corecte, avand in alcatuirea lor cel putin un sir interzis mai mic.

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

$A_{n}=3^{n}-(T_{n}+T_{n-1}+T_{n-2}+...+T_{3}+T_{2})$

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

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

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

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

Daca numarul maxim de combinatii de 7 litere este $3^{7}$ , atunci numarul de combinatii de 7 litere care nu sunt interzise este :

$A_{7}=3^{7}-(T_{7}+T_{6}+T_{5}+T_{4}+T_{3}+T_{2})$

"Cu precizie matematica !" , as spune.

Problema mea in aceasta situatie, este sa pot reduce termenul general n, $T_{n}$ ,
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.

Etcetera · « **Răspuns #17 :** Noiembrie 30, 2012, 01:12:42 p.m. »

Sau, tot prin calcule, am putea arata si asa :

Daca un sir de lungime n este interzis, atunci sunt cel mult $(m-1)(3^{m-2})$ 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 $(m-1)(3^{m-2})$ , atunci putem sa spunem ca numarul minim de siruri de lungime n care sunt corecte este egal cu:

$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]$

Este diferenta aceasta mai mare ca zero ?

zec · « **Răspuns #18 :** Decembrie 02, 2012, 12:53:34 a.m. »

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:
$A_{n+1}\ge 3A_n-A_{n-1}-\cdots -A_1-1$ .
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 $A_n\ge A_{n-1}+\cdots+A_1+1$ .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
$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)$
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:
$A_{n+1}\ge A_n-3^{n-1}-\cdots-3-1$ 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.

Etcetera · « **Răspuns #19 :** Decembrie 03, 2012, 01:49:41 p.m. »

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.

zec · « **Răspuns #20 :** Decembrie 03, 2012, 06:01:42 p.m. »

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.

Autor Subiect: O problema frumoasa (Citit de 23246 ori)

zec

Răspuns: O problema frumoasa

Etcetera

Răspuns: O problema frumoasa

Etcetera

Răspuns: O problema frumoasa

zec

Răspuns: O problema frumoasa

Etcetera

Răspuns: O problema frumoasa

zec

Răspuns: O problema frumoasa