Teorema de Popoviciu

La teorema de Popoviciu és un resultat en matemàtiques, establit per Tiberius Popoviciu, sobre el número de formes en que es pot expressar una cantitat com sumixca de múltiples d'atres dos cantitats i està relacionat en el problema de les monedes de Frobenius i establix:

Una atra forma d'interpretar la fòrmula anterior, és com el número de formes en que es pot dividir el sancer n com suma no ordenada en a on els sumants són únicament a i b. En atres paraules, dona el número de particions restringides de n en el conjunt {a, b}.

Eixemple

En el context del problema de les monedes de Frobenius, es desija trobar el número de formes de reunir $20 usant únicament monedes de $3 i $4. Com a eixemples: {$4, $4, $3, $3, $3, $3} o {$4, $4, $4, $4, $4} i podria haver unes atres.

Cada una d'elles correspon a una combinació llineal positiva en a on els coeficients són el número de voltes que s'usa cada denominació. En l'eixemple, les combinacions llineals són 2·4 + 4·3 i 5·4 + 0·3.

Aplicant la fòrmula de Popoviciu, substituïm n=20, a=3, b=4. Els números r i s deuen satisfer les equacions

$3r\equiv 1(\mathrm{mod}4),4s\equiv 1(\mathrm{mod}3)$

Una possible solució és r=3 i s=1, ya que $3\cdot 3=9\equiv 1(\mathrm{mod}4),$ i $1\cdot 4=4\equiv 1(\mathrm{mod}3)$.

Els térmens que apareixen en la teorema de Popoviciu són:

$\frac{n}{ab}=\frac{20}{3\times 4}=\frac{20}{12}=\frac{5}{3},$

$-\left\{\frac{rn}{a}\right\}=-\left\{\frac{3\cdot 20}{4}\right\}=-\left\{15\right\}=0$

$-\left\{\frac{sn}{b}\right\}=-\left\{\frac{1\cdot 20}{3}\right\}=-\frac{2}{3}$

Llavors la teorema de Popoviciu establix que el número

$\frac{n}{ab}-\left\{\frac{rn}{a}\right\}-\left\{\frac{sn}{b}\right\}+1=\frac{5}{3}-\frac{2}{3}+1=2$

és el número total de formes d'expressar 20 com a combinació llineal no negativa de 3 i 4, per lo que es conclou que les dos mostrades inicialment són les úniques possibles.