Hỏi về định lý RUF

Ng_Anh_Hoang · 29-12-2012, 10:33 PM

Xét bài toán: Cho $p$ nguyên tố lẻ. Tìm số tập con X của $M=\{1,2,...,p\}$ thỏa $p | \displaystyle \sum_{x \in X} x $.
Bài này mình dùng định lý RUF thì tìm ra đáp số là $$S=\dfrac{P(1)+P(a)+P(a^2)+...+P(a^{p-1})}{p}=\dfrac{2^p+2(p-1)}{p}=\dfrac{2^p-2}{p}+2$$
Trong đó $\begin{cases} P(x)=(1+x)(1+x^2)...(1+x^p) \\ a=\cos \dfrac{2\pi}{p}+i\sin \dfrac{2\pi}{p} \end{cases} $

Nhưng đáp số đúng của bài toán là $\dfrac{2^p-2}{p}+1$ (có thể thấy với $p=3$ thì có 3 tập thỏa là $\{3\}, \{1,2\}, \{1,2,3\}$ chứ không phải 4.)

Theo mình nguyên nhân là do RUF đã đếm luôn $a_0$, nghĩa là các tập con có tổng số phần tử là 0, là tập rỗng, nên mới dư ra 1.

Cho mình hỏi là tập rỗng trong trường hợp này có được tính không? Vì mình thấy chưa có đề bài nào chú thích về phần này.

29-12-2012, 10:33 PM	#1
Ng_Anh_Hoang +Thành Viên+ Tham gia ngày: Apr 2012 Đến từ: Dải Ngân Hà Bài gởi: 163 Thanks: 256 Thanked 59 Times in 39 Posts	Hỏi về định lý RUF Xét bài toán: Cho $p$ nguyên tố lẻ. Tìm số tập con X của $M=\{1,2,...,p\}$ thỏa $p \| \displaystyle \sum_{x \in X} x $. Bài này mình dùng định lý RUF thì tìm ra đáp số là $$S=\dfrac{P(1)+P(a)+P(a^2)+...+P(a^{p-1})}{p}=\dfrac{2^p+2(p-1)}{p}=\dfrac{2^p-2}{p}+2$$ Trong đó $\begin{cases} P(x)=(1+x)(1+x^2)...(1+x^p) \\ a=\cos \dfrac{2\pi}{p}+i\sin \dfrac{2\pi}{p} \end{cases} $ Nhưng đáp số đúng của bài toán là $\dfrac{2^p-2}{p}+1$ (có thể thấy với $p=3$ thì có 3 tập thỏa là $\{3\}, \{1,2\}, \{1,2,3\}$ chứ không phải 4.) Theo mình nguyên nhân là do RUF đã đếm luôn $a_0$, nghĩa là các tập con có tổng số phần tử là 0, là tập rỗng, nên mới dư ra 1. Cho mình hỏi là tập rỗng trong trường hợp này có được tính không? Vì mình thấy chưa có đề bài nào chú thích về phần này.