Soluții corecte: Zoltan Szabo, Ionel-Vasile Pit-Rada.
Nota: Am primit rezultate partiale de la mai multi rezolvitori. Zoltan Szabo si Vasile Trofin au considerat si cazul in care se accepta introducerea simultana a mai multor bile rosii in buzunar.
Zoltan Szabo:
Numărul break-urilor distincte de valoare cel puțin egală cu 135 este 16588569.
Break-ul maxim de 147 de puncte se obține într-un singur fel (toate bilele rosii introduse cu bile negre + toate bilele colorate). Acest exemplu îl vom folosi ca model:
Pentru a obține un break de valoare mai mare sau egală cu 135, putem avea 3 posibilități:
1. Bilele negre de valoare 7 evidențiate cu roșu în exemplul de mai sus pot fi alte bile colorate cu diferite valori din intervalul [2,7]. Bilele neevidențiate au sumă fixă (15 puncte bilele roșii și 27 de puncte bilele colorate).
2. Secvența de lovituri nu va conține primele două bile din stânga. Adică se pierde o bilă roșie și o bilă colorată în valoare de 1+7=8 puncte. Eliminarea a două bile roșii ar rezulta micșorarea rezultatului cu 16 puncte, 147-16=131<135 ceea nu se mai socotește la soluții.
3. De asemenea poate să lipsească din break ultima bilă neagră de 7 puncte. Lipsa bilelor de valoare 7+6=13 ar micșora valoarea break-ului până la 147-13=134<135, ceea nu se va socoti la soluții.
De asemenea observăm că o bilă roșie de la început și o bilă neagră de la sfârșit generează o pierdere de 8+7=15 puncte, nici acest caz nu poate intra la soluții.
Astfel ne interesează numărul de puncte și numărul de modalități ce se pot obține cu 14 respectiv 15 bile roșii succesiv.
Numărul cazurilor le vom calcula recursiv separat pentru bilele de valoare 2, 3, 4, 5, 6, 7.
Considerăm că Nk(pas, val) este numărul cazurilor de break cu valoarea bilelor colorate egală cu val în care am folosit succesiv pas lovituri pentru bilele colorate, ultima bilă colorată din break fiind de valoare k.
Avem un set de formule recursive indirecte:
N2(pas,val)=N2(pas-1,val-2)+ N3(pas-1,val-2)+ N4(pas-1,val-2)+ N5(pas-1,val-2)+ N6(pas-1,val-2)+ N7(pas-1,val-2)
N3(pas,val)=N2(pas-1,val-3)+ N3(pas-1,val-3)+ N4(pas-1,val-3)+ N5(pas-1,val-3)+ N6(pas-1,val-3)+ N7(pas-1,val-3)
N4(pas,val)=N2(pas-1,val-4)+ N3(pas-1,val-4)+ N4(pas-1,val-4)+ N5(pas-1,val-4)+ N6(pas-1,val-4)+ N7(pas-1,val-4)
N5(pas,val)=N2(pas-1,val-5)+ N3(pas-1,val-5)+ N4(pas-1,val-5)+ N5(pas-1,val-5)+ N6(pas-1,val-5)+ N7(pas-1,val-5)
N6(pas,val)=N2(pas-1,val-6)+ N3(pas-1,val-6)+ N4(pas-1,val-6)+ N5(pas-1,val-6)+ N6(pas-1,val-6)+ N7(pas-1,val-6)
N7(pas,val)=N2(pas-1,val-7)+ N3(pas-1,val-7)+ N4(pas-1,val-7)+ N5(pas-1,val-7)+ N6(pas-1,val-7)+ N7(pas-1,val-7)
Valorile inițiale fiind N2(1,2)=N3(1,3)=N4(1,4)=N5(1,5)=N6(1,6)=N7(1,7)=1. Pe celelalte valori anterioare le setăm pe 0, astfel încât formula recursivă să poată funcționa: (1,p)=0, p!=k, p=-3, -2, ....,
Deci numărul break-urilor obținute din pas lovituri la bilele colorate care realizează val puncte este
Ncolor(pas,val)=N2(pas,val) + N3(pas,val) + N4(pas,val) + N5(pas,val) + N6(pas,val) + N7(pas,val)
La această valoare se adaugă punctele obținute pe bilele roșii, respectiv pe bilele colorate de la sfârșit.
Cu ajutorul Excel-ului am calculat aceste valori:
|
Puncte |
Break complet |
Fără ultima bilă neagră |
Fără prima bilă roșie |
Total |
|
135 |
9076405 |
11628 |
2380 |
9090413 |
|
136 |
4282980 |
3060 |
560 |
4286600 |
|
137 |
1915356 |
680 |
105 |
1916141 |
|
138 |
806990 |
120 |
14 |
807124 |
|
139 |
317970 |
15 |
1 |
317986 |
|
140 |
116055 |
1 |
0 |
116056 |
|
141 |
38745 |
0 |
0 |
38745 |
|
142 |
11628 |
0 |
0 |
11628 |
|
143 |
3060 |
0 |
0 |
3060 |
|
144 |
680 |
0 |
0 |
680 |
|
145 |
120 |
0 |
0 |
120 |
|
146 |
15 |
0 |
0 |
15 |
|
147 |
1 |
0 |
0 |
1 |
|
Total |
16570005 |
15504 |
3060 |
16588569 |
Deci numărul break-urilor de valoare mai mare sau egală cu 135 este 16.588.569.
Ionel-Vasile Pit-Rada:
Orice break valid are forma
1,c[1],1,c[2],...,1,c[p],2,3,4,5,6,7
acest break este format deci din p perechi de forma(1,c[k]) cu 1<=k<=p<=15 urmate de cele 6 bile colorate. Suma unui astfel de break este egala cu S(p)=(1+c[1])+(1+c[2])+...+(1+c[p])+27. Notam cu v[k]=1+c[k] si avem 3<=v[k]<=8.
Fie X(t,k)=numarul de moduri de a obtine o suma 108<=t<=120 cu 1<=k<=15 valori din multimea {3,4,...,8}.
Observam ca:
a) X(t,k)=0 daca t<k*3 sau t>k*8
b) X(3*k,k)=1, X(8*k,k)=1
c)
X(t,k)=X(t-8,k-1)+X(t-7,k-1)+...+X(t-4,k-1)+X(t-3,k-1)
X(t+1,k)=X(t-7,k-1)+X(t-6,k-1)+X(t-5,k-1)+...+X(t-3,k-1)+X(t-2,k-1)
X(t,k)=X(t+1,k)-X(t-2,k-1)+X(k-8,k-1)
d) Pentru a se putea atinge suma cuprinsa intre 108 si 120 trebuie ca suma sa contina cel 14 sau 15 termeni.
Pentru suma 108 trebuie cel putin 10 termeni egali cu 8 (cu 9 termeni egali cu 8 si 5 termeni egali cu 7 se obtine doar 107)
Cu 14 termeni se poate obtine:
X(112,14)=1, suma 112 in mod unic 8*14=112
X(111,14)=14, suma 111 in C(14,1)=14 moduri, 13*8+7
X(110,14)=105, suma 110 in C(14,1)+C(14,2)=14+91=105, 13*8+6 sau 12*8+2*7
X(109,14)=560, suma 109 in C(14,1)+C(14,2)*2+C(14,3)=14+182+364=560 , 13*8+5 sau 12*8+7+6 sau 11*8+3*7
X(108,14)=2380, suma 108 in C(14,1)+C(14,2)*3+C(14,1)*C(13,2)+C(14,4)=14+273+14*78+1001=2380, 13*8+4 sau 12*8+2*6 sau 12*8+7+5 sau 11*8+2*7+6 sau 10*8+4*7
Total 3060 de variante cu 14 termeni.
Pentru variantele cu 15 termeni avem:
X(120,15)=1, 120=15*8
X(119,15)=15
X(118,15)=120
X(117,15)=680
X(116,15)=3060
X(115,15)=11628
X(114,15)=38745
X(113,15)=116055
X(112,15)=317970
X(111,15)=806990
X(110,15)=1915356
X(109,15)=4282980
X(108,15)=9076405
Total variante cu 14 si 15 termeni 16.573.065
Break-urile in care sunt introduse toate bilele colorate sunt in numar de 16.573.065
Break-urile in care sunt introduse toate bilele colorate cu exceptia ultimei bile negre sunt in numar de X(115,15)+X(116,15)+...+X(120,15) = 11628+3060+680+120+15+1=15504
Raspuns final: numarul break-urilor cu suma >=135 este 16.573.065 + 15504 = 16.588.569
Logic
