Cifrele 1,2,3,4,5,6,7 sunt extrase aleator dintr-o urna. Care este probabilitatea de a le extrage astfel incat la orice moment suma cifrelor extrase este nedivizibila cu 3?

De exemplu, daca extragerea se face in ordinea 4,1,6,7,3,2,5, suma primelor patru cifre extrase 4+1+6+7=18 este divizibila cu 3, iar la extragerea 1,3,4,2,6,7,5 toate sumele 1, 1+3, 1+3+4, 1+3+4+2, 1+3+4+2+6, 1+3+4+2+6+7, 1+3+4+2+6+7+5 sunt nedivizibile cu 3.

Adaptare a unei probleme propuse la concursul Putnam 2007.

Vom "transpune" problema in Z3.
Consideram "subclasele" de resturi modulo 3: 0^={3,6} , 1^={1,4,7} si 2^={2,5}.
Rationamentul este sa formam siruri care sa contina 2 de 0^, 3 de 1^ si 2 de 2^ astfel incat sumele primilor k termeni din fiecare sir sa nu fie 0^, unde k ia valori de la 1 la 7.
Sirurile nu pot sa inceapa cu 0^.
Sirurile care incep cu 1^ sunt :
1^ - 0^ - 0^ - 1^ - 2^ - 1^ - 2^
1^ - 0^ - 1^ - 0^ - 2^ - 1^ - 2^
1^ - 0^ - 1^ - 2^ - 0^ - 1^ - 2^
1^ - 0^ - 1^ - 2^ - 1^ - 0^ - 2^
1^ - 0^ - 1^ - 2^ - 1^ - 2^ - 0^
1^ - 1^ - 0^ - 0^ - 2^ - 1^ - 2^
1^ - 1^ - 0^ - 2^ - 0^ - 1^ - 2^
1^ - 1^ - 0^ - 2^ - 1^ - 0^ - 2^
1^ - 1^ - 0^ - 2^ - 1^ - 2^ - 0^
1^ - 1^ - 2^ - 0^ - 0^ - 1^ - 2^
1^ - 1^ - 2^ - 0^ - 1^ - 0^ - 2^
1^ - 1^ - 2^ - 0^ - 1^ - 2^ - 0^
1^ - 1^ - 2^ - 1^ - 0^ - 0^ - 2^
1^ - 1^ - 2^ - 1^ - 0^ - 2^ - 0^
1^ - 1^ - 2^ - 1^ - 2^ - 0^ - 0^
(o reprezentare sub forma de arbore ar fi mult mai intuitiva!)
Prin aceeasi metoda incercam sa construim siruri care incep cu 2^. Se observa repede ca nu putem sa realizam nici un astfel de sir.
Inseamna ca avem doar cele 15 siruri reprezentate mai sus. Fiecare astfel de sir poate fi construit la randul lui in 2!*3!*2!=24 moduri => putem extrage cele 7 cifre din urna in 15*24 = 360 de moduri astfel incat la orice moment suma sa nu se divida cu 3.
Cum numarul de extrageri total este 7!=5040 => probabilitatea ceruta este P=360/5040 adica 14%.

Solutie foarte buna!

Forma de concurs a problemei a fost generalizarea cu 3k+1 in loc de 7.

[Citat] Solutie foarte buna! Forma de concurs a problemei a fost generalizarea cu 3k+1 in loc de 7.

Multumesc frumos !
La o prima vedere generalizarea schimba intru-catva modul de abordare
0^={3,6,...,3k}
1^={1,4,...,3k+1}
2^={2,5,...,3k-1}
Dificultatea de fond este sa "generalizam" parcurgerea "arborilor" si sa gasim numarul total de siruri favorabile (vorbind in termenii rezolvarii anterioare)
In rest fiecare sir va fi format in k!*(k+1)!*k! moduri iar numarul total de siruri va fi (3k+1)!
O sa ma mai gandesc...

Mai m-am gandit...
A ramas sa gasim cate siruri se pot construi in cazul general.

Cand am incercat sa postez "arborele" nu mi-a iesit in forma "ramificata" si atunci am postat sirurile unul sub altul. Aceasta scriere insa este benefica pentru generalizare. Daca privim mai atenti cum sunt construite sirurile vom observa ca daca eliminam

-urile, sirurile de

si

sunt identice (normal!). Acelasi lucru se va intampla si pe cazul general...diferenta dintre ele facand-o

-urile "presarate" printre

si

.

Deasemenea si in cazul general se observa imposibilitatea de a construi siruri care sa inceapa cu

(iar cu

este evident ca nu pot sa inceapa).

Deci, ramane sa numaram sirurile care incep cu

. Avem

pozitii de ocupat si ne intereseaza doar dispunerea

-urilor pe aceste pozitii. Cum pe prima pozitie nu se poate pune

, raman

pozitii de ocupat de catre

de

,adica

. Asa cum am mentionat in mesajul anterior fiecare sir va fi format in

moduri iar numarul total de siruri va fi:

.

Inseamna ca probabilitatea ceruta va fi:

.

Solutie foarte buna a cazului general!