SoluĊ£ii corecte:  Ionel-Vasile Pit-Rada, Zoltan Szabo, Emil Claudiu Man

 

Ionel-Vasile Pit-Rada

Observatia 1: Pentru orice parola corecta se va obtine acelasi rezultat, deci este suficient sa analizam pentru parola initiala 01234567

Observatia 2: Pentru orice parola p[0],p[1],...,p[7] observam ca daca cifra p[i] este 8 sau 9 ea nu produce coliziune. Daca cifra p[i] este <= 7 atunci ea va produce o coliziune in permutarea circulara cu d=(i+8-p[i])%8 pozitii. Astfel pentru a numara coliziunile este suficient sa numaram cate coliziuni avem cu fiecare dintre permutarile circulare ale parolei initiale. De exemplu pentru parola 40216573 avem coliziunile in parolele obtinute prin permutarile circulare cu  4,1,0,2,6,0,7,4 pozitii. Deci avem maxim 2 coliziuni cu parola initiala sau cu parola permutata circular cu 4 pozitii.

 

Etapa 1:
Presupunem ca in parola de lungime 8 doua pozitii sunt rezervate pentru cifrele 8 si 9 si pentru celelalte 6 pozitii analizam in continuare. Datorita simetriei, pentru orice doua pozitii sunt

fixate se va obtine acelasi numar de asezari pentru celelalte 6 pozitii, astfel incat sa avem cel mult 3 coliziuni.

Astfel vom calcula x= numarul parolelor de lungime 6 formate doar cu cifre diferite dintre cifrele 0,1,2,3,4,5,6,7 si care au cel mult 3 coliziuni cu parola initiala sau permutari circulare ale ei. Pentru a calcula x vom genera toate aranjamentele celor 8 cifre luate cate 6 si pentru fiecare aranjament a[0],a[1],...,a[5] vom numara coliziunile conform observatiei 2.
Astfel obtinem 1152 parole care au 1 coliziune , 13024 parole care au 2 coliziuni si 5040 parole care au 3 coliziuni, deci in total 19216 parole care au cel mult 3 coliziuni cu parola initiala sau permutarile circulare ale ei.

Vom putea astfel obtine x*56 parole de lungime 8 care au cel mult 3 coliziuni si care contin fiecare ambele cifre 8 si 9.

 

Etapa 2:
Presupunem ca in parola de lungime 8 o pozitie este rezervata pentru una dintre cifrele 8 sau 9 si pentru celelalte 7 pozitii analizam in continuare. Datorita simetriei, pentru orice pozitie am avea fixata se va obtine acelasi numar de asezari pentru celelalte 7 pozitii, astfel incat sa avem cel mult 3 coliziuni.

Astfel vom calcula y= numarul parolelor de lungime 7 formate doar cu cifre diferite dintre  cifrele 0,1,2,3,4,5,6,7 si care au cel mult 3 coliziuni cu parola initiala sau cu permutarile circulare ale ei. Pentru a calcula y vom genera toate aranjamentele celor 8 cifre luate cate 7 si pentru fiecare aranjament a[0],a[1],...,a[6] vom numara coliziunile conform observatiei 2.
Astfel obtinem 512 parole care au 1 coliziune , 22064 parole care au 2 coliziuni si 14096 parole care au 3 coliziuni, deci in total 36672 parole care au cel mult 3 coliziuni cu parola initiala sau permutarile circulare ale ei.

Vom putea astfel obtine y*16 parole de lungime 8 care au cel mult 3 coliziuni si care contin fiecare una dintre cifrele 8 si 9.

 

Etapa 3:
Vom calcula z= numarul parolelor de lungime 8 formate cu toate cifrele 0,1,2,3,4,5,6,7 si care au cel mult 3 coliziuni cu parola initiala sau cu permutarile circulare ale ei. Pentru a calcula z vom genera toate permutarile celor 8 cifre si pentru fiecare permutare a[0],a[1],...,a[7] vom numara coliziunile conform observatiei 2.
Astfel obtinem 0 parole care au 1 coliziune , 16912 parole care au 2 coliziuni si 17280 parole care au 3 coliziuni, deci in total 34192 parole care au cel mult 3 coliziuni cu parola initiala sau permutarile circulare ale ei si care nu contin niciuna dintre cifrele 8 si 9.


Putem acum calcula numarul cerut NR = x*56 + y*16 + z = 19216*56 + 36672*16 + 34192 = 1697040

Raspuns final 1697040