Matematică şi Logică > Matematică - probleme generale
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:
--- Citat din: zec din Noiembrie 24, 2012, 02:33:58 a.m. ---Doua siruri interzise diferite au intodeauna lungimi diferite.
--- Terminare citat ---
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.
Navigare
[#] Pagina următoare
Du-te la versiunea completă