Home/ Intrebari/Q 92490
Urmator
In Process

AniDeȘcoală.ro Latest Intrebari

Felixx
veteran (III)
Pe: 2018-01-13T12:26:13+02:00 In: In:

Probleme de numarare

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.

Similare

4 raspunsuri

  1. gigelmarga
    profesor

    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 3C_5^3+5^3=155.

  2. Felixx
    veteran (III)

    Multumesc,domnule gigelmarga.

  4. gigelmarga
    profesor

    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 \epsilon o radacina de ordinul 3 a unitatii diferită de 1 și P(x)=\prod_{k=1}^{15}(x-\epsilon^k)=(x^3-1)^5=x^{15}-5x^{12}+10x^9-10x^6+5x-1.

    Din relațiile lui Viete deducem că s=\sum_{1\le i<j<k\le 15}\,\epsilon^i \epsilon^j \epsilon^k=5. Pe de altă parte, s=a_0+a_1\epsilon+a_2\epsilon^2, unde a_t este numărul tripletelor (i,j,k) cu i+j+k=t \mod 3.

    Ne interesează, desigur, a_0. Să observăm că a_0+a_1+a_2=C_{15}^3. Cum a_0-5+a_1\epsilon +a_2\epsilon^2=0, iar \epsilon e o rădăcină a ecuației x^2+x+1=0, deducem că a_0-5=a_1=a_2.

    De aici, a_0=\frac13\left(C_{15}^3+10\right)=155.

  5. Felixx
    veteran (III)

    Frumoasa expunere. Multumesc.

Raspunde

Raspunde