probleme de matematica rezolvate algoritmic

Rezolvăm probleme de matematică... folosind calculatorul Titlul articolului de față poate induce în eroare. Există multe probleme interesante în care calculatorul își dovedește utilitatea. Cele pe care dorim însă să le exemplificăm aici reprezintă situații în care folosirea unui algoritm de rezolvare - și rularea acestuia într-un mediu de dezvoltare (am ales Eclipse și limbajul Java) – se dovedesc imperios necesare (deși la o primă vedere nu s-ar părea). Înainte de toate, enunțurile problemelor. P1. Câte numere naturale de cinci cifre au suma cifrelor cel mult egală cu 10 ? (Culegere pt. clasa a IV-a, Gardin-Berechet, Ed. Paralela 45, 2009, pag. 23)

P2. Determinaţi numerele naturale 0 1 2 8, , ,...,a a a a , elemente ale mulţimii { }0,1,2,3, 4 şi x

număr natural, astfel încât 0

0a ≠ şi

8 7 6 5 4 3 2 1 0

0 1 2 3 4 5 6 7 82012a x a x a x a x a x a x a x a x a x+ + + + + + + + =

(Ion Safta, E:14409, G.M.B. 11/2012) P3. Să se determine mulțimile nevide A și B de numere naturale, care satisfac simultan condițiile :

i. { }2A B∩ =

ii. Cel mai mare element al mulțimii A B∪ este cel mult egal cu 6; iii. Pentru orice a A∈ există b B∈ astfel încât a b+ este pătrat perfect; iv. Pentru orice b B∈ există a A∈ astfel încât b a− este pătrat perfect. (Adriana și Lucian Dragomir, E:13746, G.M.B. 12/2008; culegere Mate-2000 Consolidare, clasa a V-a, partea I, ediția a II-a, Ed. Paralela 45, 2013, pag. 158) Problema P1 Se observă repede că suma cifrelor unui număr n de cinci cifre ia valori cuprinse între 1 (în cazul singular al numărului 10000) și 45 (pentru 99999n = ). Căutând o regulă după care să formăm numere de cinci cifre având suma cifrelor 2, 3, 4, ..., ajungem repede la o analiză complicată.

Pentru suma cifrelor 2, avem tuplurile ( )2,0,0,0,0 și ( )1,1,0,0,0 . Primului tuplu îi

corespunde doar numărul 20000, cel de-al doilea generează soluțiile 10001,10010,10100 și

11000 . Sunt în total cinci numere de cinci cifre cu suma cifrelor 2.

Suma cifrelor 3 este produsă de tuplurile ( ) ( )3,0,0,0,0 , 2,1,0,0,0 și ( )1,1,1,0,0 . Primul

tuplu corespunde doar lui 30000, al doilea generează 10002,10020,10200,12000, 20001,

20010, 20100 și 21000 , iar al treilea produce soluțiile 10011,10101,10110,11001,11010 și

11100 . Cu suma cifrelor 3 avem 1 8 6 15+ + = numere de cinci cifre.

Tuplurile de 5 cifre cu suma 4 sunt ( ) ( ) ( ) ( )4,0,0,0,0 , 3,1,0,0,0 , 2, 2,0,0,0 , 2,1,1,0,0 și

( )1,1,1,1,0 . Lor le corespund soluțiile: 40000,10003,10030,10300,13000, 30001, 30010,

30100, 31000, 20002, 20020, 20200, 22000,10012,10021,10102,10120,10201,10210,

11002,11020,11200,12001,12010,12100, 20011, 20101, 20110, 21001, 21010, 21100,

10111,11011,11101 și 11110 . În total, sunt 1 8 4 18 4 35+ + + + = de numere de 5 cifre cu suma cifrelor egală cu 4. Dacă nu v-a ajuns (mie mi-a ajuns cu vârf și îndesat), luați și tuplurile cu sumă 5 :

( )5,0,0,0,0 , ( ) ( ) ( ) ( ) ( )4,1,0,0,0 , 3,2,0,0,0 , 3,1,1,0,0 , 2, 2,1,0,0 , 2,1,1,1,0 și ( )1,1,1,1,1 .

Acestea trebuie să producă 70 de numere de cinci cifre cu suma egală cu 5. Răbdare și tutun, eu pe prima am isprăvit-o, iar al doilea nu m-a pasionat nicicând. E clar că nu e rezonabil să producem toate numerele de cinci cifre având suma cifrelor cel mult egală cu 10 pentru a le număra ulterior. Posibil să fie vreun algoritm mai ”smart” de numărare, dar cel puțin la o primă vedere un astfel de algoritm nu este la îndemână. În pană de idei, apelăm la prietenul (și totodată inamicul) omului modern, computerul. Presupunem o minimală cunoaștere a unui limbaj de programare; codul Java care urmează (cât și cel de la problema P2) poate fi cu ușurință rescris în C. public class SfCalculator {

protected static int sumOfFigures(int n) {

int sum = 0, r = 0;

do {

r = n % 10;

sum += r;

n = n/10;

}

while (n != 0);

return sum;

}

public static void main(String[] args) {

int ns;

for (int k = 1; k <= 45; k++)

{

ns = 0;

for (int i = 10000; i <= 99999; i++) {

if (sumOfFigures(i) <= k)

ns++;

}

System.out.println("ns[" + k + "] = " + ns);

}

}

}

Am denumit clasa SfCalculator (de la ”Sum of Figures Calculator”). Metoda statică sumOfFigures() calculează suma cifrelor numărului n , primit ca parametru. Aceasta împarte succesiv numărul n la 10, reținând restul împărțirii, adică ultima cifră. Împărțirea continuă cât timp câtul nu devine 0, ceea ce se întâmplă după un număr de pași egal cu numărul cifrelor lui n . Între timp, în variabila sum se acumulează suma cifrelor lui n . Metoda main(), apelabilă din exterior, parcurge toate valorile posibile ale sumei cifrelor (de la 1 la 45, așadar). Pentru fiecare dintre acestea, se parcurg într-o buclă interioară toate numerele de cinci cifre (de la 10000 la 99999), incrementând variabila interioară ns pentru fiecare număr având suma cifrelor cel mult egală cu valoarea k la care s-a ajuns în bucla exterioară. Algoritmul nu este foarte eficient, dar rulează destul de repede. Rezultatele afișate sunt : ns[1] = 1

ns[2] = 6

ns[3] = 21

ns[4] = 56

ns[5] = 126

ns[6] = 252

ns[7] = 462

ns[8] = 792

ns[9] = 1287

ns[10] = 2001 Există prin urmare 2001 numere de cinci cifre având suma cifrelor cel mult egală cu 10. Este evident că problema nu e chiar deloc de clasa a IV-a. Prezența ei în culegerea Gardin-Berechet (altminteri un material de calitate bună) este cel puțin bizară. Exercițiu. Modificați algoritmul astfel încât să caute doar numere cu cifre nenule. Chiar și așa, rămân destule numere de cinci cifre cu suma cifrelor cel mult egală cu 10 (pentru a satisface anumite curiozități, sunt 252). Problema P2

Deoarece 83 6561 2012= > , rezultă 2x ≤ . Nu putem lua 0x = , deoarece 0

0 este o operaţie

fără sens. Pentru 1x = , membrul stâng se scrie 0 1 8

... 9 4 36a a a+ + + ≤ × = , deci nu poate

avea valoarea 2012. Rezultă 2x = ; se înlocuiesc valorile puterilor lui 2 şi egalitatea dată devine:

0 1 2 3 4 5 6 7 8256 128 64 32 16 8 4 2 2012a a a a a a a a a+ + + + + + + + =

Avem 1 2 3 4 5 6 7 8

128 64 32 16 8 4 2a a a a a a a a+ + + + + + + ≤

( )4 128 64 32 16 8 4 2 1 4 255 1020≤ ⋅ + + + + + + + = ⋅ =

Dacă 0

3a ≤ , atunci 0

256 256 3 768a ≤ ⋅ = , deci :

0 1 2 3 4 5 6 7 8256 128 64 32 16 8 4 2 1020 768 1788 2012a a a a a a a a a+ + + + + + + + ≤ + = <

şi egalitatea nu poate avea loc. Rezultă că 0

4a = .

Dacă 1

3a ≤ , atunci 0 1

256 128 256 4 128 3 1024 384 1408a a+ ≤ ⋅ + ⋅ = + = . Restul sumei se

majorează prin 2 3 4 5 6 7 8

64 32 16 8 4 2a a a a a a a+ + + + + + ≤

( )4 64 32 16 8 4 2 1 4 127 508≤ ⋅ + + + + + + = ⋅ = , deci :

0 1 2 3 4 5 6 7 8256 128 64 32 16 8 4 2 1408 508 1916 2012a a a a a a a a a+ + + + + + + + ≤ + = <

Deducem că şi 1

4a = . Dacă 2

3a ≤ , atunci 0 1 2

256 128 64 256 4 128 4 64 3a a a+ + ≤ ⋅ + ⋅ + ⋅ =

1024 512 192 1536 192 1728= + + = + = . Restul sumei se majorează prin :

( )3 4 5 6 7 832 16 8 4 2 4 32 16 8 4 2 1 4 63 252a a a a a a+ + + + + ≤ ⋅ + + + + + = ⋅ = . Prin

adunarea celor două părţi, obţinem :

0 1 2 3 4 5 6 7 8256 128 64 32 16 8 4 2 1728 252 1980 2012a a a a a a a a a+ + + + + + + + ≤ + = <

Rezultă că şi 2

4a = . Presupunem 3

3a ≤ şi rezultă 0 1 2 3

256 128 64 32a a a a+ + + ≤

256 4 128 4 64 4 32 3 1024 512 256 96 1536 352 1888≤ ⋅ + ⋅ + ⋅ + ⋅ = + + + = + =

Restul sumei se majorează prin ( )4 5 6 7 816 8 4 2 4 16 8 4 2 1a a a a a+ + + + ≤ ⋅ + + + + =

4 31 124= ⋅ = . Cum 1888 124 2012+ = , obţinem o primă soluţie a problemei, notată

( )4,4,4,3, 4, 4, 4, 4, 4 . Faptul că 4 5 6 7, , ,a a a a şi

8a au valori maxime ne arată că nu mai există

alte soluţii pentru 3

3a ≤ . Putem lua în continuare şi 3

4a = .

Calculăm în acest caz ( )0 1 2 3256 128 64 32 4 256 128 64 32a a a a+ + + = ⋅ + + + =

4 480 1920= ⋅ = . Rezultă prin diferenţă că :

( )4 5 6 7 816 8 4 2 2012 1920 92 1a a a a a+ + + + = − =

Este dificil în continuare să intuim câte soluții ar avea ecuația diofantică în 5 variabile la care s-a ajuns. Se pot face observații care limitează considerabil spațiul de căutare (de altfel, vom continua cu soluția ”clasică” îndată ce vom prezenta algoritmul care ”produce” soluțiile ecuației). public class SumOfPowers {


int nsol = 0;

for (int i = 0; i <= 4; i++)

for (int j = 0; j <= 4; j++)

for (int k = 0; k <= 4; k++)

for (int l = 0; l <= 4; l++)

for (int m = 0; m <= 4; m++)

if (92 == (16 * i + 8 * j + 4 * k + 2 * l + m)) {

System.out.println("Sol [" + (++nsol) + "]: [" + i + ", "

+ j + ", " + k + ", " + l + ", " + m + "]");

}

System.out.println("Found " + nsol + " solutions.");

}

}

Clasa denumită SumOfPowersDemo (îmi pare rău, n-am avut o inspirație mai bună în ce privește numele !) conține o singură metodă main(), apelabilă din exterior. Fiecare buclă for()

corespunde uneia dintre necunoscutele 4 5 6 7, , ,a a a a și

8a . Expresia calculată în condiția

instrucțiunii if() este comparată cu valoarea țintă 92 din membrul drept al ecuației ( )1 . Pentru

fiecare tuplu ( )4 5 6 7 8, , , ,a a a a a care verifică egalitatea se afișează valorile celor cinci variabile,

precedate de numărul de ordine nsol, util pentru a vedea câte soluții sunt exact. Rularea metodei de mai sus produce rezultatul : Sol [1]: [2, 4, 4, 4, 4]

Sol [2]: [3, 2, 4, 4, 4]

Sol [3]: [3, 3, 2, 4, 4]

Sol [4]: [3, 3, 3, 2, 4]

Sol [5]: [3, 3, 3, 3, 2]

Sol [6]: [3, 3, 3, 4, 0]

Sol [7]: [3, 3, 4, 0, 4]

Sol [8]: [3, 3, 4, 1, 2]

Sol [9]: [3, 3, 4, 2, 0]

Sol [10]: [3, 4, 0, 4, 4]

Sol [11]: [3, 4, 1, 2, 4]

Sol [12]: [3, 4, 1, 3, 2]

Sol [13]: [3, 4, 1, 4, 0]

Sol [14]: [3, 4, 2, 0, 4]

Sol [15]: [3, 4, 2, 1, 2]

Sol [16]: [3, 4, 2, 2, 0]

Sol [17]: [3, 4, 3, 0, 0]

Sol [18]: [4, 0, 4, 4, 4]

Sol [19]: [4, 1, 2, 4, 4]

Sol [20]: [4, 1, 3, 2, 4]

Sol [21]: [4, 1, 3, 3, 2]

Sol [22]: [4, 1, 3, 4, 0]

Sol [23]: [4, 1, 4, 0, 4]

Sol [24]: [4, 1, 4, 1, 2]

Sol [25]: [4, 1, 4, 2, 0]

Sol [26]: [4, 2, 0, 4, 4]

Sol [27]: [4, 2, 1, 2, 4]

Sol [28]: [4, 2, 1, 3, 2]

Sol [29]: [4, 2, 1, 4, 0]

Sol [30]: [4, 2, 2, 0, 4]

Sol [31]: [4, 2, 2, 1, 2]

Sol [32]: [4, 2, 2, 2, 0]

Sol [33]: [4, 2, 3, 0, 0]

Sol [34]: [4, 3, 0, 0, 4]

Sol [35]: [4, 3, 0, 1, 2]

Sol [36]: [4, 3, 0, 2, 0]

Sol [37]: [4, 3, 1, 0, 0]

Found 37 solutions. 37 de soluții și cu cea găsită anterior 38 !!! Curat de clasa a V-a era problema asta. Pariez că sub 1% din elevii de clasa a X-a de la ”Mate-Info” sunt în stare să o rezolve complet. De altfel, rezolvarea ”oficială” din G.M.B. se mulțumește cu găsirea unei singure soluții. Să vedem în continuare cum ar putea continua o rezolvare ”clasică”, care să producă cele 37 de soluții generate de către algoritm.

Dacă 4

2a ≤ , atunci 4

16 32a ≤ , dar ( )5 6 7 88 4 2 4 8 4 2 1 4 15 60a a a a+ + + ≤ ⋅ + + + = ⋅ = ⇒

4 5 6 7 8

16 8 4 2 92a a a a a⇒ + + + + ≤ . Egalitatea are loc numai dacă 4

2a = şi

5 6 7 84a a a a= = = = ; ajungem la soluţia ( )4,4,4,4,2, 4, 4, 4, 4

Fie 4

3a ≥ , adică { }43, 4a ∈ . Pentru a limita spaţiul de căutare a soluţiilor egalităţii ( )1 , facem

următoarele observaţii :

a) 8

a nu poate fi impar, deoarece toţi ceilalţi termeni sunt pari. Rezultă { }80, 2, 4a ∈ .

b) Cum ( )4 5 6 4 5 616 8 4 4 4 2a a a a a a+ + = ⋅ + + se împarte exact la 4, la fel ca şi 92, suma

rămasă, adică 7 8

2a a+ , trebuie să fie multiplu de 4. Din cele 25 de valori posibile pentru

perechea ( )7 8,a a , această condiţie este satisfăcută de următoarele 8 :

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }0,0 , 0, 4 , 1, 2 , 2,0 , 2,4 , 3, 2 , 4,0 , 4, 4

Spaţiul de căutare pentru tuplurile de forma ( )4 5 6 7 8, , , ,a a a a a care satisfac relaţia ( )1 este

limitat la 2 5 5 8 400⋅ ⋅ ⋅ = de valori (deoarece 4

a ia două valori, 5

a şi 6

a câte 5, iar perechea

( )7 8,a a poate lua 8 valori). Alcătuim următorul tabel, în care pe ultima coloană punem “expresia

ţintă“ 4 5 6 7 8

16 8 4 2a a a a a+ + + + . Strategia este de a calcula numai valorile “promiţătoare” ale

acesteia, astfel încât să reducem şi mai mult numărul de valori calculate.

4a

5a

6a

7a

8a

4 5 6 7 816 8 4 2a a a a a+ + + +

3 0,1,2 X X X Omise din calcul ; produc valori prea mici (vezi soluţia

( )3, 2, 4, 4, 4

3 2 4 4 4 16 3 8 2 4 4 2 4 4 48 16 16 8 4 92× + × + × + × + = + + + + = 3 3 0,1,2 X X Omise din calcul ; produc valori prea mici - vezi soluţia

( )3,3, 2, 4, 4

3 3 2 4 4 16 3 8 3 4 2 2 4 4 48 24 8 8 4 92× + × + × + × + = + + + + =

3 3 3 Tripleta ( )3,3,3 produce o contribuţie de

16 3 8 3 4 3 48 24 12 84× + × + × = + + = ; până la 92 , mai trebuie 8 92 84= − , care se realizează pentru perechile

( ) ( )2, 4 , 3, 2 şi ( )4,0 - vezi următoarele trei linii

3 3 3 2 4 16 3 8 3 4 3 2 2 4 48 24 12 4 4 92× + × + × + × + = + + + + = 3 3 3 3 2 16 3 8 3 4 3 2 3 2 48 24 12 6 2 92× + × + × + × + = + + + + = 3 3 3 4 0 16 3 8 3 4 3 2 4 0 48 24 12 8 92× + × + × + × + = + + + = 3 3 4 Tripleta ( )3,3, 4 produce o contribuţie de



3 3 4 0 4 16 3 8 3 4 4 2 0 4 48 24 16 4 92× + × + × + × + = + + + = 3 3 4 1 2 16 3 8 3 4 4 2 1 2 48 24 16 2 2 92× + × + × + × + = + + + + = 3 3 4 2 0 16 3 8 3 4 4 2 2 0 48 24 16 4 92× + × + × + × + = + + + = 3 4 0 X X Omise din calcul ; produc valori prea mici - vezi soluţia

( )3, 4, 0, 4, 4

3 4 0 4 4 16 3 8 4 4 0 2 4 4 48 32 8 4 92× + × + × + × + = + + + = 3 4 1 Tripleta ( )3, 4,1 produce o contribuţie de



3 4 1 2 4 16 3 8 4 4 1 2 2 4 48 32 4 4 4 92× + × + × + × + = + + + + = 3 4 1 3 2 16 3 8 4 4 1 2 3 2 48 32 4 6 2 92× + × + × + × + = + + + + = 3 4 1 4 0 16 3 8 4 4 1 2 4 0 48 32 4 8 92× + × + × + × + = + + + = 3 4 2 Tripleta ( )3, 4, 2 produce o contribuţie de



3 4 2 0 4 16 3 8 4 4 2 2 0 4 48 32 8 4 92× + × + × + × + = + + + = 3 4 2 1 2 16 3 8 4 4 2 2 1 2 48 32 8 2 2 92× + × + × + × + = + + + + = 3 4 2 2 0 16 3 8 4 4 2 2 2 0 48 32 8 4 92× + × + × + × + = + + + = 3 4 3 0 0 16 3 8 4 4 3 2 0 0 48 32 12 92× + × + × + × + = + + = 3 4 3,4 X X Omise din calcul ; produc valori prea mari - vezi soluţia

( )3, 4,3, 0,0

4 0 X X X Omise din calcul ; produc valori prea mici - vezi soluţia

( )4,0, 4, 4, 4

4 0 4 4 4 16 4 8 0 4 4 2 4 4 64 16 8 4 92× + × + × + × + = + + + = 4 1 0,1,2 X X Omise din calcul ; produc valori prea mici - vezi soluţia

( )4,1, 2, 4, 4

4 1 2 4 4 16 4 8 1 4 2 2 4 4 64 8 8 8 4 92× + × + × + × + = + + + + = 4 1 3 Tripleta ( )4,1,3 produce o contribuţie de



4 1 3 2 4 16 4 8 1 4 3 2 2 4 64 8 12 4 4 92× + × + × + × + = + + + + = 4 1 3 3 2 16 4 8 1 4 3 2 3 2 64 8 12 6 2 92× + × + × + × + = + + + + = 4 1 3 4 0 16 4 8 1 4 3 2 4 0 64 8 12 8 92× + × + × + × + = + + + = 4 1 4 Tripleta ( )4,1, 4 produce o contribuţie de



4 1 4 0 4 16 4 8 1 4 4 2 0 4 64 8 16 4 92× + × + × + × + = + + + = 4 1 4 1 2 16 4 8 1 4 4 2 1 2 64 8 16 2 2 92× + × + × + × + = + + + + = 4 1 4 2 0 16 4 8 1 4 4 2 2 0 64 8 16 4 92× + × + × + × + = + + + = 4 2 0 X X Omise din calcul ; produc valori prea mici - vezi soluţia

( )4, 2,0, 4, 4

4 2 0 4 4 16 4 8 2 4 0 2 4 4 64 16 8 4 92× + × + × + × + = + + + = 4 2 1 Tripleta ( )4, 2,1 produce o contribuţie de



4 2 1 2 4 16 4 8 2 4 1 2 2 4 64 16 4 4 4 92× + × + × + × + = + + + + = 4 2 1 3 2 16 4 8 2 4 1 2 3 2 64 16 4 6 2 92× + × + × + × + = + + + + = 4 2 1 4 0 16 4 8 2 4 1 2 4 0 64 16 4 8 92× + × + × + × + = + + + = 4 2 2 Tripleta ( )4, 2, 2 produce o contribuţie de



4 2 2 0 4 16 4 8 2 4 2 2 0 4 64 16 8 4 92× + × + × + × + = + + + = 4 2 2 1 2 16 4 8 2 4 2 2 1 2 64 16 8 2 2 92× + × + × + × + = + + + + = 4 2 2 2 0 16 4 8 2 4 2 2 2 0 64 16 8 4 92× + × + × + × + = + + + = 4 2 3 0 0 16 4 8 2 4 3 2 0 0 64 16 12 92× + × + × + × + = + + = 4 2 3,4 X X Omise din calcul ; produc valori prea mari - vezi soluţia

( )4, 2,3, 0,0

4 3 0 Tripleta ( )4,3,0 produce o contribuţie de

16 4 8 3 4 0 64 24 88× + × + × = + = ; până la 92 , mai trebuie 4 92 88= − , care se realizează pentru perechile


4 3 0 0 4 16 4 8 3 4 0 2 0 4 64 24 4 92× + × + × + × + = + + = 4 3 0 1 2 16 4 8 3 4 0 2 1 2 64 24 2 2 92× + × + × + × + = + + + = 4 3 0 2 0 16 4 8 3 2 2 0 64 24 4 92× + × + × + = + + = 4 3 1 0 0 16 4 8 3 4 1 2 0 0 64 24 4 92× + × + × + × + = + + = 4 3,4 1,2,3,4 X X Omise din calcul ; produc valori prea mari - vezi soluţia

( )4,3,1,0, 0

În concluzie, problema are 38 de soluţii. Primele două sunt obţinute anterior tabelului, celelalte

36 de obţin prin concatenarea de ( )4, 4, 4,4 în faţa celor obţinute în tabelul de mai sus.

Mulţimea soluţiilor problemei este aşadar :

( ) ( ) ( ){ 4, 4, 4,3,4,4,4,4,4 , 4, 4, 4, 4, 2, 4, 4, 4, 4 , 4,4,4,4,3, 2, 4, 4, 4 ,S =

( ) ( ) ( )4,4,4, 4,3,3,2,4,4 , 4,4,4,4,3,3,3,2,4 , 4, 4, 4, 4,3,3,3,3, 2 ,

( ) ( ) ( )4,4,4, 4,3,3,3, 4,0 , 4,4,4, 4,3,3,4,0,4 , 4,4,4,4,3,3,4,1, 2 ,

( ) ( ) ( )4,4,4, 4,3,3,4,2,0 , 4,4,4,4,3, 4,0,4,4 , 4,4, 4, 4,3, 4,1, 2, 4 ,

( ) ( ) ( )4,4,4, 4,3, 4,1,3,2 , 4,4,4, 4,3, 4,1, 4,0 , 4, 4, 4, 4,3,4,2,0, 4 ,

( ) ( ) ( )4,4,4, 4,3, 4, 2,1, 2 , 4, 4,4,4,3,4, 2, 2,0 , 4,4,4, 4,3, 4,3,0,0 ,

( ) ( ) ( )4,4,4, 4, 4,0,4,4,4 , 4, 4, 4, 4, 4,1, 2, 4, 4 , 4,4,4,4,4,1,3, 2, 4 ,

( ) ( ) ( )4,4,4, 4, 4,1,3,3,2 , 4,4,4,4,4,1,3, 4,0 , 4,4,4, 4, 4,1,4,0,4 ,

( ) ( ) ( )4,4,4, 4, 4,1,4,1,2 , 4,4,4,4, 4,1,4,2,0 , 4,4,4,4,4,2,0,4,4 ,

( ) ( ) ( )4,4,4, 4, 4, 2,1, 2, 4 , 4, 4, 4,4,4,2,1,3,2 , 4, 4, 4, 4, 4, 2,1, 4,0 ,

( ) ( ) ( )4,4,4, 4, 4, 2, 2,0,4 , 4, 4, 4, 4, 4, 2, 2,1, 2 , 4, 4, 4,4,4,2,2,2,0 ,

( ) ( ) ( )4,4,4, 4, 4, 2,3,0,0 , 4,4, 4, 4, 4,3,0,0,4 , 4, 4, 4, 4, 4,3,0,1, 2 ,

( ) ( )}4,4,4, 4, 4,3,0, 2,0 , 4, 4, 4, 4, 4,3,1,0,0

Tuturor acestora le corespunde 2x = . Problema P3 Începem cu câteva observații care ne fac viața mai ușoară:

a. { }, 0,1, 2,3,4,5,6A B T⊆ =

b. Dacă un element x T∈ , diferit de 2, aparține mulțimii A , el nu poate face parte și din B și

viceversa. Altminteri s-ar încălca restricția ca { }2A B∩ = .

c. Nu putem avea 0 B∈ . Ar trebui să existe a A T∈ ⊂ astfel ca 0 a− să fie pătrat perfect. Singura șansă este ca 0a = , ceea ce duce la 0 A B∈ ∩ , contradicție. d. (Strategie) Fiecare element adăugat în A (respectiv în B ) ”cere” prezența altui element (sau altor elemente) în mulțimea opusă pentru a satisface condițiile problemei. Valorile pătrate perfecte pe care le pot lua suma a b+ și diferența b a− , unde ,a A b B∈ ∈ sunt 0, 1, 4 și 9. În consecință, putem alcătui tabelul ”cine cere pe cine” de mai jos. Cu roșu am marcat restricțiile datorate observației ii).

a A∈ Pe cine cere în B b B∈ Pe cine cere în A 0 0, 1 sau 4 0 0 1 0 sau 3 1 0 sau 1 2 2 2 1 sau 2 3 1 sau 6 3 2 sau 3 4 0 sau 5 4 0, 3 sau 4 5 4 5 1, 4 sau 5 6 3 6 2, 5 sau 6

Cu toate observațiile prețioase de mai sus, numărul potențialelor soluții ale problemei rămâne

mare. Pentru mulțimea A există 62 64= de posibilități de generare (deoarece, cu excepția lui 2,

toate celelalte șase numere naturale cel mult egale cu 6 pot sau nu aparține mulțimii); fiecăreia îi

corespund mai multe sau mai puține submulțimi B astfel încât { }2A B∩ = . Este nerezonabil

să producem toate variantele de mulțimi A , de exemplu și să căutăm apoi – pentru fiecare dintre acestea - toate submulțimile B care satisfac restricțiile iii) și iv) din enunț. Cu ochiul liber se pot

”dibui” câteva dintre ele (cea mai vizibilă fiind { }2A B= = ) – ceea ce face și soluția prezentată

în G.M.B. 6/2009, unde se indică opt variante. public class TwoSetProblem {

private static final int[] T = {0, 1, 3, 4, 5, 6};

private BitSet aset = new BitSet(6);

private BitSet bset = new BitSet(6);

private int nsol = 0;

private boolean isSquare(int x) {

return (x == 0 || x == 1 || x == 4 || x == 9);

}

private boolean isSolution(Set<Integer> a, Set<Integer> b) {

boolean bSolution = true;

for (Integer i : a) {

boolean bFound_b = false;

for (Integer j : b) {

if (isSquare(i+j)) {

bFound_b = true;

break;

}

}

if (! bFound_b)

return false;

}

for (Integer j : b) {

boolean bFound_a = false;

for (Integer i : a) {

if (isSquare(j-i)) {

bFound_a = true;

break;

}

}

if (! bFound_a)

return false;

}

return true;

}

private void displaySet(Set<Integer> s) {

StringBuilder bld = new StringBuilder();

if (s.isEmpty()) {

System.out.println(new String(new char[] {'\u00D8'}));

return;

}

bld.append("{");

for (Integer e : s) {

bld.append(e);

bld.append(", ");

}

System.out.print(bld.substring(0, bld.length()-2) + "}");

}

private List<Set<Integer>> generateASet() {

List<Set<Integer>> result = new ArrayList<Set<Integer>>();

for (int i = 0; i <= 63; i++) {

byte[] ba = new byte[] {(byte)i};

aset = BitSet.valueOf(ba);

Set<Integer> currentA = new HashSet<Integer>();

currentA.add(2);

for (int k = 0; k < 6; k++) {

if (aset.get(k))

currentA.add(T[k]);

}

result.add(currentA);

}

return result;

}

private void generateBSet(Set<Integer> aaset) {

Set<Integer> witness = new HashSet<Integer>();

witness.add(2);

for (int i = 0; i <= 63; i++) {

byte[] bb = new byte[] {(byte)i};

bset = BitSet.valueOf(bb);

Set<Integer> currentB = new HashSet<Integer>();

currentB.add(2);

for (int k = 0; k < 6; k++) {

if (bset.get(k))

currentB.add(T[k]);

}

Set<Integer> copyOfB = new HashSet<Integer>(currentB);

copyOfB.retainAll(aaset); // Intersect each generated B with A

if (copyOfB.equals(witness)) {

if (isSolution(aaset, currentB)) {

System.out.print("Found solution " + (++nsol) + ": A = ");

displaySet(aaset);

System.out.print(", B = ");

displaySet(currentB);

System.out.println();

}

}

}

}


TwoSetProblem pb = new TwoSetProblem();

List<Set<Integer>> asets = pb.generateASet();

for (Set<Integer> asset : asets) {

pb.generateBSet(asset);

}

}

}

De data asta, codul e ceva mai lung. Nici aici nu facem caz de eficiența algoritmului folosit. Câteva explicații sunt însă necesare. Metoda isSquare() întoarce true dacă parametrul primit

este pătrat perfect; în cazul de față, este suficient să verificăm că acesta este unul din pătratele perfecte care se pot obține din operații de tipul a b+ sau b a− , cu a A∈ și b B∈ . Metoda isSolution() testează dacă mulțimile de întregi A și B , primite ca parametri, reprezintă o soluție a problemei date; în fapt, se verifică restricțiile iii) și iv) din enunț. Metoda displaySet() afișează mulțimea primită ca parametru; în cazul în care aceasta este vidă, se afișează caracterul Ø, având codul ASCII D8. Nucleul rezolvării este consituit din metodele generateASet() și generateBSet(). Prima produce toate mulțimile A posibile și le întoarce într-o listă de mulțimi. Pentru aceasta, folosim clasa BitSet din Java și metoda statică valueOf(), care construiește un BitSet pornind de la un tabel de valori byte. Într-o buclă se iterează de la 0 la 63, ceea ce în binar corespunde valorilor pe 6 biți 000000 până la 111111, generând astfel toate submulțimile ale căror elemente sunt luate din vectorul static T = {0, 1, 3, 4, 5, 6}, la care se adaugă 2. Metoda generateBSet() folosește același algoritm și generează toate submulțimile B posibile, după care verifică dacă acestea formează împreună cu mulțimea A , primită ca parametru, o soluție a problemei. Este necesară păstrarea unei cópii a mulțimii currentB în copyOfB, pentru efectuarea operației de intersecție (retainAll), care șterge elementele necomune. Înainte de a apela metoda isSolution(), se verifică (condiția i) din enunț) dacă intersecția este egală cu o mulțime-martor în care avem doar elementul 2. În fine, iată și rezultatele afișate. Found solution 1: A = {2}, B = {2}

Found solution 2: A = {2}, B = {2, 3}

Found solution 3: A = {2}, B = {2, 6}

Found solution 4: A = {2}, B = {2, 3, 6}

Found solution 5: A = {0, 2}, B = {1, 2}

Found solution 6: A = {0, 2}, B = {1, 2, 3}




Found solution 10: A = {0, 2}, B = {1, 2, 3, 4}






Found solution 16: A = {0, 2}, B = {1, 2, 3, 4, 6}





Found solution 21: A = {0, 1, 2}, B = {2, 3, 4}

Found solution 22: A = {0, 1, 2}, B = {2, 3, 4, 5}


Found solution 24: A = {0, 1, 2}, B = {2, 3, 4, 5, 6}



Found solution 27: A = {0, 2, 3}, B = {1, 2}
















Found solution 43: A = {0, 2, 3, 4}, B = {1, 2, 5}

Found solution 44: A = {0, 2, 3, 4}, B = {1, 2, 5, 6}




























Found solution 72: A = {0, 1, 2, 5, 6}, B = {2, 3, 4}

Problema are nu mai puțin de 72 de soluții. Nu ne mai obosim să includem vreo rezolvare ”clasică”. E limpede că aceasta nu este la îndemâna multora, soluțiile fiind ușor de omis.

probleme de matematica rezolvate algoritmic

Documents