Deci problema suna asa:Cate numere de n cifre nu au 3 cifre consecutive egale?

Sursa: "cineva" caruia i-a dat-o "altcineva", deci din pacate din start sursa este indoielnica, dar problema pare interesanta.
Se poate rezolva fara mari dificultati pe cazuri particulare n=3,4,5,6, dar in cazul general pare foarte complicat.
Ideea ar fi sa excludem numerele "rele"-care au 3 cifre egale, sau 4 cifre egale, etc.
Doar ca dificultatea care apare este faptul ca in acelasi numar "rau" pot fi mai multe blocuri de 3 cifre egale de exemplu 11102222567333....etc.

Eu m-am gandit asa.
Notam :
B_1={numere care au cifrele de pe pozitiile 1,2,3 egale}
B_2={numere c are au cifrele de pe pozitiile 2,3,4 egale}
...
B_{n-2}={numere care au cifrele de pe ultimele 3 pozitii egale}
Atunci toate numerele care nu verifica cerintele problemei sunt cele din
Reuniunea multimilor B_1,B_2,...B_n.
Problema este insa ca aceste multimi nu sunt disjuncte, deci trebuie aplicat principiul includerii si exc luderii, moment la care mi-am prins urechile cand vreau sa calculez cardinalul intersectiei a k multimi din acelea.
Adica ar merge, desi anevoios dar ar merge ptr valori mici ale lui n, dar in cazul general intru in ceata )
Deci daca vede cineva vreo solutie rapida, ii multumesc. Daca nu, nu )
Sau poate as putea fac e o numarare prin recurenta?

O secventa (finita) de cifre (in baza zece) este "permisa" daca satisface conditia ca orice trei termeni consecutivi sa nu fie toti trei egali intre ei.

(Problema din enunt este putin altfel, este vorba de secvente ce nu incep cu zero... Cumva trebuie acel cineva sa strice structura combinatorica.)

Putem acum mai departe pune conditia ca prima cifra sa nu fie nula. Sau nu...
Numim aceste secvente care raman permise.

Fie A(n) numarul de secvente permise de lungime n care se termina in doua cifre diferite.

Fie B(n) numarul de secvente permise de lungime n care se termina in doua cifre egale (intre ele).

Avem o recurenta simpla, dupa ce avem grija sa calculam
A(1) si
B(1) .
(Cu sau fara conditia ca prima cifra din secventa sa fie nenula...)

Problema propusa are deci

A(1) = 9, am exclus 0.
B(1) = 0,

A(n+1) = 9A(n) + 9B(n)
B(n+1) = A(n)

Introducem S(n) = A(n) + B(n).
Rezulta imediat recurenta

S(n+2) = A(n+2) + B(n+2) = 9S(n+1) + A(n+1) = 9S(n+1) + 9S(n) .

De aici totul este simplu, ecuatia caracteristica este
x² - 9x - 9 = 0 ,
fie a si b radacinile ei
si termenul general S(n) se exprima liniar (cu aceleasi constante ce nu depind de n) in functie de puterile de ordin n ale radacinilor a si b.

Din S(1) = 9 si S(2) = 90 rezulta mai departe
S(3) = 9S(2) + 9S(1) = 891 cum ne si asteptam de fapt. (900 de numere de trei cifre, din care eliminam 111, 222, 333, ... , 999 la numaratoare.)

Multumesc. Am inteles cum e cu acea recurenta.
Totusi cum putem vorbi despre numere de o cifra cu 2 cifre diferite? )

Stiu, propozitiile trebuie alese ceva mai pedant, daca trebuie sa fie scrise la o olimipiada pentru a evita orice depunctare.

In acest caz rescriu:

Fie n > 0 natural.

[Citat] Fie A(n) numarul de secvente permise de lungime n care se termina in doua cifre diferite pot fi extinse prin "alaturare a unei cifre pe ultimul loc" la un numar permis cu ultimele doua cifre egale intre ele. Fie B(n) numarul de secvente permise de lungime n care se termina in doua cifre egale (intre ele) NU pot fi extinse prin "alaturare a unei cifre pe ultimul loc" la un numar permis cu ultimele doua cifre egale intre ele.

Putem face matematica si asa.
(Dar acesta este motivul principal pentru care oamenii pleaca de la matematica. Prea mare precizie conduce des la prea putina intelegere. Pana la urma si bourbakistii au ramas doar unul.)

Propozitiile scrise devin chiar si mai nastrusnice daca vrem sa le facem sa functioneze si pentru n=0...