Săptămâna 411

Sizin üçün oyun:

Google Play'də əldə edin


Yüklə 75.69 Kb.
tarix31.10.2017
ölçüsü75.69 Kb.

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 ak numarul numerelor “balansate” avand 2k cifre . Prin urmare numarul total al numerelor “balansate” va fi . Pentru a-l determina pe ak, 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 *()2 . 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 ak = *()2 - ** , k = 1, 2,.. 5 si deci in final vom avea : . Efectuand calculele necesare, obtinem a1=45, a2=2160, a3=64800, a4=907200 si a5=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: a1,a2,…,an şirespectiv r1,r2,…,rn.

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 a1 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 a1 şi o bilă roşie

  2. Să folosim bila a1 ş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, ... , 104 } . 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 = 104*(104+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<104, 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 4k 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 4k moduri. Prin urmare avem pentru 2k cifre un numar de * 4k * 4k = 4 2k numere.

Avem deci cazurile :

1) are 2 cifre à *42= 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 à *44= 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 .

Dostları ilə paylaş:
Orklarla döyüş:

Google Play'də əldə edin


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©muhaz.org 2017
rəhbərliyinə müraciət

    Ana səhifə