Săptămâna 411

Rezolvare:
Soluţia 1 (Ştefan Gaţachiu, Gheorghe Oprea, Maria Negru):

Un număr care să îndeplinească cele două condiţii trebuie să fie format dintr-un număr par de cifre: 2, 4, 6, 8 sau 10 cifre.

Vom considera separat cazul numerelor formate din două cifre:

- dacă prima cifră este pară, iar celaltă este impară:

- pentru cifra pară avem 4 moduri de a o alege: 2, 4, 6, 8 (numărul nu poate începe cu 0)

- pentru cifra impară avem 5 moduri de a o alege: 1, 3, 5, 7, 9

Aplicând regula produsului, rezultă că se pot forma numere.

- dacă prima cifră este impară, iar cealaltă pară, atât pentru cifra impară cât şi pentru cea pară avem câte 5 moduri de alegere, în total numere.

Rezultă că se pot forma 45 numere cu două cifre.
Fie acum un număr format cu 2n cifre, , cu n cifre pare şi n cifre impare.

Vom considera o aşezare oarecare a cifrelor în cadrul numărului (este vorba de poziţia cifrelor, nu de valoarea lor)

Din cele 5 cifre pare se pot alege n cifre pare în moduri (aici e posibil să apară şi numere care încep cu 0, dacă numărul începe cu o cifră pară; aceste numere le vom scădea la sfârşit). La fel, cifrele impare pot fi alese în moduri. Astfel, pentru o poziţionare a cifrelor pare şi impare avem numere.

Întrucât prin schimbarea poziţiilor cifrelor pare şi a celor impare se obţin numere diferite, rezultă că pentru orice altă poziţionare a cifrelor numărului se pot forma tot numere. Deci trebuie să calculăm numărul de moduri în care se pot poziţiona cifrele. Vom lua în discuţie doar cifrele pare, deoarece cele impare se vor aşeza pe poziţiile rămase. Cele n cifre pare se pot poziţiona pe cele 2n poziţii ale numărului în moduri.

Deci, în total (inclusiv numerele care încep cu 0) avem numere.

Acum trebuie să vedem câte încep cu 0.

Fixăm 0 pe prima poziţie. Deci trebuie să vedem câte numere de cifre se pot forma cu cifre pare şi n cifre impare. Judecând într-un mod analog cu cel de mai sus obţinem numere.

Deci, cu 2n cifre se pot forma numere.

Pentru n = 2: 2160 numere

Pentru n = 3: 64800 numere

Pentru n = 4: 907200 numere

Pentru n = 5: 3265920 numere

În total sunt 45 + 2160 + 64800 + 907200 + 3265920 = 4240125 numere balansate.

O soluţie similară a dat Nicolae Ady, care sumarizează rezultatele într-un tabel:.

A	B	C	D	E	F	G	H
Cifre (A)	Numar variante ce satisfac conditia 1 (Combinari de 10 luate cate A)	Numar variante ce satisfac conditia 2	Numar variante ce NU contin cifra "0"	Numar variante ce contin cifra "0"	Numere Balansate pentru variantele ce NU contin cifra "0" (Aranjamente de A luate cate A)	Numere Balansate pentru variantele ce contin cifra "0" F * (A-1) / A	Total Numere Balansate D * F + E * G
2	45	25	20	5	2	1	45
4	210	100	60	40	24	18	2160
6	210	100	40	60	720	600	64800
8	45	25	5	20	40320	35280	907200
10	1	1	0	1	3628800	3265920	3265920
							4240125

Nicolae Ady: Dacă prima cifră a unui număr balansat poate fi şi 0, atunci:

A	B	C	D	E
Cifre (A)	Numar variante ce satisfac conditia 1 (Combinari de 10 luate cate A)	Numar variante ce satisfac conditia 2	Numere Balansate pentru fiecare varianta (Aranjamente de A luate cate A)	Total Numere Balansate C * D
2	45	25	2	50
4	210	100	24	2400
6	210	100	720	72000
8	45	25	40320	1008000
10	1	1	3628800	3628800
				4711250

Soluţia 2 (George Schiopescu):

Pentru numerele de 10 cifre avem 10! combinatii posibile dintre care 9! combinatii incep cu 0  10!-9!=9!(10-1)=9!* 9 numere balansate de 10 cifre.

Pentru numerele de 8 cifre avem doua variante:

1. 
   Sa nu folosim cifra 0 si un numar impar nu vom folosi perechile (0,1),(0,3),(0,5),(0,7),(0,9)
   
2. 
   Sa nu folosim o cifra para diferita de 0 si un numar impar  nu vom folosi perechile (2,1),(2,3),(2,5),(2,7),(2,9), (4,1),(4,3),(4,5),(4,7),(4,9), (6,1), (6,3), (6,5), (6,7), (6,9), (8,1), (8,3), (8,5), (8,7), (8,9).
   

În primul caz obtinem 8! * 5 numere, iar in al doilea caz 7! * 7 * 4 * 5=140 * 7!

Deci in total 8! * 5+140 * 7! = 180 * 7! numere balansate de 8 cifre.

Pentru numerele de 6 cifre avem doua variante:

1. 
   Sa folosim 3 cifre pare diferite de 0 si 3 cifre impare  vom folosi tripletele (2,4,6),(2,4,8),(2,6,8),(4,6,8) si 10 triplete de numere impare.
   
2. 
   Sa folosim 3 cifre pare, dintre care una egala cu 0 si 3 cifre impare  vom folosi tripletele (2,4,0),(2,6,0),(2,8,0),(4,6,0),(4,8,0),(6,8,0) si 10 triplete de numere impare.
   

În primul caz obtinem 6! * 4 * 10=40 * 6! numere, iar in al doilea caz 5! * 5 * 6 * 10 = 50 * 6!

Deci in total 40 * 6! + 50 * 6! = 90 * 6! numere balansate de 6 cifre

Pentru numerele de 4 cifre avem doua variante:

1. 
   Sa folosim 2 cifre pare diferite de 0 si 2 cifre impare  vom folosi perechile (2,4),(2,6),(2,8),(4,6),(4,8),(6,8) si 10 perechi de numere impare
   
2. 
   Sa folosim 2 cifre pare, dintre care una egala cu 0 si 2 cifre impare  vom folosi perechile (0,2), (0,4), (0,6), (0,8) şi 10 perechi de numere impare
   

În primul caz obtinem 4! * 6 * 10 = 60 * 4! numere , iar in al doilea

3 * 3! * 4 * 10 = 30 * 4!

Deci in total 60 * 4!+ 30 * 4! = 90 * 4! numere balansate de 4 cifre.
Pentru numerele de 2 cifre avem doua variante:

1. 
   Sa folosim cifra 0 si un numar impar numérele 10, 30, 50, 70, 90
   
2. 
   Sa folosim o cifra para diferita de 0 si un numar impar numérele 12, 14, 16, 18, 32, 34, 36, 38, 52, 54, 56, 58, 72, 74, 76, 78, 92, 94, 96, 98 şi rasturnatele lor
   

În primul caz obtinem 5 numere iar in al doilea caz 40.

Deci in total 5 + 40 = 45 numere balansate de 2 cifre.

TOTAL:

9! * 9 + 180 * 7! + 90 * 6! + 90 * 4! + 45 = 3265920 + 907200 + 64800 + 2160 + 45 = 4240125

Soluţia 3 (Cătălin Hancu):

Din prima conditie din enunt rezulta ca numerele au cel mult 10 cifre, iar din a doua ca au un numar par de cifre, deci vor avea 2k cifre, cu k = 1..5.

Notam cu a_k numarul numerelor “balansate” avand 2k cifre . Prin urmare numarul total al numerelor “balansate” va fi . Pentru a-l determina pe a_k, observam ca cifrele pare se plaseaza pe k pozitii din cele 2k. Alegerea acestor k pozitii se poate face in moduri. Pentru o astfel de alegere, cifrele pare 0,2,4,6,8 se pot distribui pe acele k pozitii in moduri, iar pentru fiecare astfel de distributie cifrele impare 1,3,5,7,9 pot fi plasate pe cele k pozitii ramase tot in moduri. In total numarul de posibilitati va fi deci *()² . Trebuie insa sa tinem cont de faptul ca plasarea lui 0 pe prima dintre cele 2k pozitii nu convine, deci eliminam toate aceste posibilitati. Daca 0 este pe prima pozitie, raman 4 numere pare de plasat pe k-1 pozitii si cele impare apoi pe k pozitii. Rationand ca mai sus obtinem ** posibilitati.

Prin urmare a_k = *()² - ** , k = 1, 2,.. 5 si deci in final vom avea : . Efectuand calculele necesare, obtinem a₁=45, a₂=2160, a₃=64800, a₄=907200 si a₅=3265920 si prin urmare vom avea in final ca numarul tuturor numerelor “balansate” este N = 4240125.

Soluţia 4 (Monica Oprina):

Am gasit N = 4.240.125 numere balansate

Pentru rezolvarea problemei se pot folosi fie aplicatii realizate in diverse medii de programare (eu am apelat la PHP), fie Excel (aceasta metoda este mult mai greoaie decat programarea).

In cazul programarii, am realizat aplicatia de mai jos folosind PHP, dar calculatorul a lucrat greu pentru numerele formate din 10 cifre (probabil ca un calculator mai puternic s-ar descurca mai bine). Pentru numerele formate din 8 si 10 cifre am folosit programul pe serii de numere, nu pentru tot intervalul, pentru a scurta timpul de procesare si apoi am generalizat de la o serie de numere la intreg intervalul.

Din fiecare numar din serie, am extras cifrele numarului respectiv, am pus conditia ca toate cifrele sa fie diferite intre ele, apoi am verificat paritatea cifrelor extrase si am adunat in variabila $par cifrele pare ale numarului si in variabila $impar cifrele impare ale numarului. La final, daca numarul de cifre pare este egal cu numarul de cifre impare, numarul respectiv indeplineste conditiile problemei si crestem variabila de numarare a numerelor balansate cu 1 unitate ($n=$n+1).



$n=0;

for ($numar=1000000000;$numar<=1999999999;$numar++)

{$par=0;

$impar=0;

$c1=substr($numar,0,1);

$c2=substr($numar,1,1);

$c3=substr($numar,2,1);

$c4=substr($numar,3,1);

$c5=substr($numar,4,1);

$c6=substr($numar,5,1);

$c7=substr($numar,6,1);

$c8=substr($numar,7,1);

$c9=substr($numar,8,1);

$c10=substr($numar,9,1);

if ($c1!=$c2 AND $c1!=$c3 AND $c1!=$c4 AND $c1!=$c5 AND $c1!=$c6 AND $c1!=$c7 AND $c1!=$c8 AND $c1!=$c9 AND $c1!=$c10 AND

$c2!=$c3 AND $c2!=$c4 AND $c2!=$c5 AND $c2!=$c6 AND $c2!=$c7 AND $c2!=$c8 AND $c2!=$c9 AND $c2!=$c10 AND

$c3!=$c4 AND $c3!=$c5 AND $c3!=$c6 AND $c3!=$c7 AND $c3!=$c8 AND $c3!=$c9 AND $c3!=$c10 AND

$c4!=$c5 AND $c4!=$c6 AND $c4!=$c7 AND $c4!=$c8 AND $c4!=$c9 AND $c4!=$c10 AND

$c5!=$c6 AND $c5!=$c7 AND $c5!=$c8 AND $c5!=$c9 AND $c5!=$c10 AND

$c6!=$c7 AND $c6!=$c8 AND $c6!=$c9 AND $c6!=$c10 AND

$c7!=$c8 AND $c7!=$c9 AND $c7!=$c10 AND

$c8!=$c9 AND $c8!=$c10 AND

$c9!=$c10)

{if( $c1%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c2%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c3%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c4%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c5%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c6%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c7%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c8%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c9%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if( $c10%2==0 ) {$par=$par+1;}

else {$impar=$impar+1;}

if ($par= =$impar) {$n=$n+1;}}

}

print $n;

?>
Folosind programul de mai sus am aflat ca exista:

• 
  45 numere balansate de 2 cifre
  
• 
  2.160 numere balansate de 4 cifre
  
• 
  64.800 numere balansate de 6 cifre
  
• 
  907.200 numere balansate de 8 cifre
  
• 
  3.265.920 numere balansate de 10 cifre
  

Adica un total de N = 4240125 numere balansate
Daca folosim Excel pentru a rezolva problema, ideea de rezolvare este aceeasi: scriem numerele pe o coloana si in coloanele urmatoare extragem cifrele numarului folosind functia:

- - MID (A1;1;1)

Apoi trebuie sa verificam daca cifrele extrase sunt pare sau nu si folosim functia:

SUMPRODUCT((MOD(aria cifrelor numarului;2)<>0)+0) – cifre impare

SUMPRODUCT((MOD(aria cifrelor numarului;2)=0)+0) – cifre pare
Acum verificam daca cifrele sunt toate diferite intre ele si daca numarul cifrelor impare din numar este egal cu numarul cifrelor pare. Daca cele doua valori sunt egale si toate cifrele sunt diferite intre ele, completam cu 1, daca nu, scriem 0. Apoi facem suma pe coloana cu conditia finala si obtinem numarul de numere balansate.
Insa la utilizarea Excel apare problema limitarii, in sensul ca nu se poate genera un numar prea mare de numere, dar se poate lucra tot pe intervale de numere, se afla numarul de numere balansate pe un interval de numere, dupa care se poate afla numarul de numere balansate pe intreg intervalul.

Generalizare (George Schiopescu):

Pornind de la cazul 5 numere pare , 5 numere impare am vrut sa generalizez.

Cum însă nu există mai mult de 5 cifre pare, am modificat puţin enunţul şi am folosit n bile albe şi n bile roşii, având scrise pe ele numere de la 1 la n , (n > 2).

Enunţ:

Avem n bile albe şi n bile roşii numerotate de la 1 la n: a₁,a₂,…,a_n şirespectiv r₁,r₂,…,r_n.

Pe acestea le putem aşeza în diverse formaţiuni în care numărul bilelor albe este egal cu numărul bilelor roşii.

Câte astfel de formaţiuni putem obţine în total, ştiind că bila albă pe care este scris numărul 1 are un defect şi nu poate fi folosită pe prima poziţie?
Solutie

Notez C(a,b) = combinari de a luate câte b

S(a=1,b) = suma de la a = 1 la b (nu am reusit sa scriu in Word toate formulele si am decis sa folosesc aceste prescurtari).
Pentru formatiunile de 2n cifre avem 2n! combinatii posibile dintre care (2n-1)! combinatii incep cu a₁  2n!-(2n-1)! = (2n-1)! * (2n-1) formatiuni posible cu 2n bile.
Pentru formatiunile de 2n-2 bile avem doua variante:

1. 
   Sa nu folosim bila a1 si o bila rosie
   
2. 
   Sa nu folosim o bila alba diferita de a1 si o bila rosie
   

În primul caz obtinem (2n-2)! * C(n-1;0) * C(n;1) formatiuni iar in al doilea

(2n-3)! * (2n-3) * C(n-1;1) * C(n;1).
Pentru formatiunile de 2n -4 bile avem doua variante:

1. 
   Sa nu folosim bila a1 si inca o bila alba precum si doua bile rosii
   
2. 
   Sa nu folosim 2 bile albe diferite de a1si 2 bile rosii
   

În primul caz obtinem (2n-4)! * C(n-1;1) * C(n;2) formatiuni iar in al doilea

(2n-5)! * (2n-5) * C(n-1;2) * C(n;2)

Pentru formatiunile de 2n-6 bile avem doua variante:

1. 
   Sa nu folosim bila a1 si inca 2 bila albe precum si trei bile rosii
   
2. 
   Sa nu folosim 3 bile albe diferite de a1si 3 bile rosii
   

În primul caz obtinem (2n-6)! * C(n-1;2) * C(n;3) formatiuni iar in al doilea

(2n-7)! * (2n-7) * C(n-1;3) * C(n;3).

……………………………………………………………………………………………

Pentru formatiunile de 2n - (2n - 2) = 2 bile avem doua variante:

1. 
   Sa folosim o bila alba diferita de a₁ şi o bilă roşie
   
2. 
   Să folosim bila a₁ şi încă o bilă roşie
   

În primul caz obtinem 2! * C(n-1,n-1) * C(n;n-1) formatiuni iar in al doilea

1! * 1 * C(n-1;n-1) * C(n;n-1).

Deci numarul total de formatiuni va fi:

(2n-1) * (2n-1)! + S(k=1,n-1)[(2n - 2k)! * C(n-1; k-1) * C(n; k) + (2n - 2k-1) * (2n - 2k - 1)! * C(n-1;k) * C(n;k)] , n > 2.
Caz particular: n = 5 

(2 * 5 - 1) * (2 * 5 - 1)! + S(k=1, 5 - 1)[(2 * 5 - 2k)! * C(5-1; k - 1) * C(5; k) + (2 * 5 - 2k - 1) * (2 * 5 - 2k - 1)! * C(5-1; k) * C(5; k)] = 9! * 9 + (8! * 5 + 7! * 7 * 4 * 5) + (6! * 4 * 10 + 5! * 5 * 6 * 10) + (4! * 6 * 10 + 3! * 3 * 4 * 10) + (2! * 4 * 5 + 1! * 1 * 1 * 5) =

9! * 9 + 180 * 7! + 6! * 90 + 4! * 90 + 45 = 3265920 + 907200 + 64800 + 2160 + 45 = 4240125.
Cătălin Hancu completează:

Utilizând o idee asemănătoare celei din problema cu numerele balansate, obţinem problema de mai jos:

Considerăm mulţimea M ={ 1, 2 ,3, ... , 10⁴ } . Notăm cu X cea mai mare submulţime a lui M cu proprietatea că orice element îndeplineşte cel puţin una din condiţiile :

1. 
   x conţine cel puţin o cifră din mulţimea {0 ,9} ;
   
2. 
   x are mai multe cifre pare decât cifre impare;
   
3. 
   x are mai multe cifre impare decât cifre pare;
   

Aflaţi suma tuturor elementelor mulţimii X.
Soluţie :

Este clar ca X contine toate elementele lui M ce verifica cel putin una dintre conditiile (i)-(iii) . Cum = 10⁴*(10⁴+1) / 2 = 50005000 , iar in mod evident avem = - , va fi suficient sa calculam . Observam mai intai ca implica faptul ca x nu indeplineste niciuna dintre conditiile (i)-(iii), si deci x contine numai cifre din multimea { 1 ,2,..., 7, 8 } iar numarul cifrelor pare si impare din x este acelasi. Prin urmare ,cum x<10⁴, x poate avea 2 sau 4 cifre.

In general, pentru 2k cifre, numerele cu aceasta proprietate se pot construi astfel : alegem cele k pozitii pe care se vor plasa cifrele pare 2,4,6 sau 8, putem, face asta in moduri. Pentru o astfel de alegere, cifrele pare, in numar de 4, se pot plasa in 4^k moduri – numarul de functii {1,2,...k} à {1,2,3,4} , iar apoi cele impare 1,3,5,7 se pot plasa pe cele k pozitii ramase tot in 4^k moduri. Prin urmare avem pentru 2k cifre un numar de * 4^k * 4^k = 4 ^2k numere.

Avem deci cazurile :

1) are 2 cifre à *4²= 32 numere de acest tip. Cum

à si deci vom avea 16 perechi a cate doua

numere cu suma 99, in total numerele de doua cifre din M\X avand suma

99*16 = 1584;
2) are 4 cifre à *4⁴= 1536 numere de acest tip. Cum

à si deci vom avea 768 perechi a cate

doua numere cu suma 9999 , in total numerele de 4 cifre din M\X

avand suma 9999 * 768 = 7679232
Ca urmare, = 1584 + 7679232 = 7680816 si atunci :

= - = 50005000 – 7680816 = 42324184 .