Một bài đếm sử dụng định lý RUF

[cloner]

Tìm số tập con A của tập $X=\{1;2;3;...;2012\} $ sao cho tổng các phần tử của A chia hết cho 5

Mình làm đến đây nhưng không biết làm tiếp, mong mọi người giúp đỡ

Xét $f(x)=(1+x)(1+x^2)...(1+x^{2012}) $, như vậy dùng định lý RUF thì có được đáp số bài toán là $S=\frac{1}{5}(f(1)+f(\xi)+f(\xi^2)+f(\xi^3)+f(\xi^ 4))-1 $ trong đó $\xi $ là căn bậc 5 của đơn vị.
Đến đây mình lại không biết tính $f(\xi),f(\xi^2),f(\xi^3),f(\xi^4) $ như thế nào

Cảm ơn mọi người nhiều
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[TrauBo]

Nguyên văn bởi cloner

Tìm số tập con A của tập $X=\{1;2;3;...;2012\} $ sao cho tổng các phần tử của A chia hết cho 5

Mình làm đến đây nhưng không biết làm tiếp, mong mọi người giúp đỡ

Xét $f(x)=(1+x)(1+x^2)...(1+x^{2012}) $, như vậy dùng định lý RUF thì có được đáp số bài toán là $S=\frac{1}{5}(f(1)+f(\xi)+f(\xi^2)+f(\xi^3)+f(\xi^ 4))-1 $ trong đó $\xi $ là căn bậc 5 của đơn vị.
Đến đây mình lại không biết tính $f(\xi),f(\xi^2),f(\xi^3),f(\xi^4) $ như thế nào

Cảm ơn mọi người nhiều

Nhận xét là $$f(\xi)=[ (1+\xi)(1+\xi^2)(1+\xi^3)(1+\xi^4)(1+\xi^5)]^{402}(1+\xi^{2011})(1+\xi^{2012})=[ (1+\xi)(1+\xi^2)(1+\xi^3)(1+\xi^4)(1+\xi^5)]^{402}(1+\xi)(1+\xi^2)$$
Do $\xi^i = \xi^j$ nếu $i \equiv j \mod 5$.
Vậy ta tính sổ cái mũ 402...
Xét $g(x)=x^5-1=(x-\xi)(x-\xi^2)...(x-\xi^5)$ thì $(1+\xi)(1+\xi^2)(1+\xi^3)(1+\xi^4)(1+\xi^5) = -g(-1)=- ( (-1)^5-1)=2$
Và nhận xét thêm là cái đống mũ 402 này vẫn xuất hiện trong $f(\xi^2), f(\xi^3), f(\xi^4)$, vì 5 là số nguyên tố nên $(1+\xi)(1+\xi^2)...(1+\xi^{2010})=(1+\xi^j)(1+\xi ^{2j})...(1+\xi^{2010j})$ nếu $(j;5)=1$.
Tới đây bạn thử làm tiếp xem có trục trặc gì thì nói TrauBo nhé
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]