Probleme de numarare

[Felixx]

Cate din submultimile multimii {1,2,...,15} au exact trei elemente a caror suma este divizibila cu 3 ?
Solutie:
Numarul de submultimi cu 3 elemente este combinari de 15 luate cate 3,adica 455 submultimi.
Din {a,b,c} cu 3l(a+b+c) rezulta a+b+c=3k, unde (a+b+c)max=13+14+15=42 ,atunci k=2-16
Presupunand a<b<c si analizand toate cazurile gasim tripletele.
1)k=2,a+b+c=6 a=1,b+c=5 {a,b,c}={1,2,3}
2)k=3,a+b+c=9, a=1,b+c=8 {1,2,6},{1,3,5}
a=2,b+c=7 {2,3,4}
etc... si "muncitoreste" gasim toate tripletele.

EXISTA O ALTA METODA MAI RAPIDA DE A DETERMINA ACESTE SUBMULTIMI ?
Multumesc.

[gigelmarga]

Da, există. Trebuie văzut ce resturi la împărțirea cu 3 dau numerele a,b,c din {1,2,3,..,15} astfel ca suma lor să se dividă cu 3.
Rezultatul final este

[Felixx]

Multumesc,domnule gigelmarga.

[gigelmarga]

O soluție alternativă (aparent mai complicată, dar care poate fi aplicată într-un caz mai general, cu un număr prim p în loc de 3 și kp în loc de 15) folosește numere complexe și polinoame.

Astfel, fie o radacina de ordinul 3 a unitatii diferită de 1 și

Din relațiile lui Viete deducem că Pe de altă parte, unde este numărul tripletelor cu

Ne interesează, desigur, Să observăm că Cum iar e o rădăcină a ecuației deducem că


De aici,

[Felixx]

Frumoasa expunere. Multumesc.