Sottoinsiemi di ${1,\ldots,2000}$

[elgiovo]

Si trovi il numero di sottoinsiemi di ${1,\ldots,2000}$ tali che la somma dei loro elementi sia divisibile per $5$.

[Steven11]

E' giusto
$(2^2000-1)/5$
?
Se si, posto lo svolgimento.

[elgiovo]

"Steven":E' giusto
$(2^2000-1)/5$
?

Purtoppo non è giusto.

[Steven11]

Doh!

[TomSawyer1]

Io ho ottenuto $(2^2000+2^402)/5$. Più generalmente, il numero di sottoinsiemi di ${1,...,5n}$ i cui elementi si sommano a $0 (mod5)$ dovrebbe essere $(2^{5n}+2^{n+2})/5$.

[elgiovo]

"TomSawyer":Io ho ottenuto $(2^2000+2^402)/5$. Più generalmente, il numero di sottoinsiemi di ${1,...,5n}$ i cui elementi si sommano a $0 (mod5)$ dovrebbe essere $(2^{5n}+2^{n+2})/5$.

E' giusto!

[TomSawyer1]

Io ho usato la ricorsione $f(5k+5)=8f(5k)+6g(5k)$, dove $f(n)$ è il numero di sottoinsiemi di ${1,...,n}$ i cui elementi si sommano a $0(mod5)$ e $g(n)$ il numero di quelli i cui elementi non si sommano a $0(mod5)$. Tu come hai fatto?

[elgiovo]

Ho considerato la biiezione tra ogni sottoinsieme ${a_1,a_2,\ldots,a_m}$ e il termine $x^(a_1)x^(a_2) ldots x^(a_m)$ del polinomio

$f(x)=(1+x)(1+x^2)ldots(1+x^(5n))$,

si cerca infatti la somma $S$ dei coefficienti dei termini $x^(5k)$, $k in NN$.
Sia $xi=e^(2pi i backslash 5)$. Vale $xi^5=1$, e inoltre $1+xi+xi^2+xi^3+xi^4=0$, quindi

$S=1/5 sum_(j=1)^5 f(xi^j)$.

$xi,xi^2,xi^3,xi^4,xi^5=1$ sono le radici di $g(x)=x^5-1$, da cui

$g(-1)=-2=(-1-xi)(-1-xi^2)(-1-xi^3)(-1-xi^4)(-1-xi^5)$,

nonchè

$(1+xi)(1+xi^2)(1+xi^3)(1+xi^4)(1+xi^5)=2$.

Per quanto detto $f(xi^j)=2^n$, per $j=1,2,3,4$. Infine $f(xi^5)=f(1)=2^(5n)$. Segue allora

$S=1/5 (4 cdot 2^n + 2^(5n))=(2^(n+2)+2^(5n))/5$.