Chủ đề này có 1 trả lời

[Trang Luong]

Cho $p$ là số nguyên tố lẻ. Hỏi có bao nhiêu tập con $A$ của $S=\left \{ 1,2,3,...2p \right \}$ sao cho tổng các phần tử của $A$ chia hết cho $p$

Bài viết đã được chỉnh sửa nội dung bởi Trang Luong: 17-04-2015 - 21:29

[tap lam toan]

Bổ đề: Cho $p$ là một số nguyên tố, đặt $\alpha =\textrm{cos}\dfrac{2\pi }{p}+i\textrm{sin}\dfrac{2\pi }{p}$. Nếu $a_{0},a_{1},...,a_{p-1}$ là các số thực thỏa
$$a_{0}+a_{1}\alpha +...+a_{p-1}\alpha ^{p-1}=0$$
Thì $$a_{0}=a_{1}=...=a_{p-1}$$
Trở lại bài toán
Gọi $\alpha =\textrm{cos}\dfrac{2\pi }{p}+i\textrm{sin}\dfrac{2\pi }{p}$, đặt $A=\left \{ X\subset S,\left |X  \right |=k \right \}$, trong đó $1 \leq k \leq 2p$
và $A_{i}=\left \{ X\in A,S(X)\equiv i (\textrm{modp}) \right \}$ với $i=0,1,...,p-1$
Xét đa thức $P(x)=(x-\alpha )(x-\alpha ^{2})...(x-\alpha^{2p} )$. Khai triển đa thức $P(x)$ theo 2 cách
  Cách 1  $P(x)=(x-\alpha )(x-\alpha ^{2})...(x-\alpha^{2p} )=\sum _{X\in A}(-1)^{k}.x^{2p-k}.\alpha ^{S(X)}$ . Khi đó hệ số của $x^{2p-k}$ là $a_{2p-k}=(-1)^{k}.\alpha ^{S(X)}$, (1)
   Cách 2: vì $\left \{ p+1,p+2,...,2p \right \}\equiv \left \{ 1,2,...,p \right \}  (\textrm{modp})$ nên
$$P(x)=\prod _{i=1}^{p}(x-\alpha ^{i})\prod _{j=p+1}^{2p}(x-\alpha ^{j})=\left ( \prod _{i=1}^{p}(x-\alpha ^{i}) \right )^{2}=(x^{p}-1)^{2}=x^{2p}-2x^{p}+1$$
(Do $\alpha ^{p+i}=\alpha ^{i}$ và $x^{p}-1=\prod _{i=1}^{p}(x-\alpha ^{i})$ do tập nghiệm của 2 đa thức này trùng nhau),   (2)
Từ (1) và (2), suy ra
+Nếu $k=p$ thì $a_{2p-k}=a_{p}=-2=(-1)^{p}\sum _{X\in A}\alpha ^{S(X)}$ Do đó
$$|A_{0}|+|A_{1}|\alpha +...+|A_{p-1}|\alpha ^{p-1}=2\Rightarrow |A_{0}|-2=|A_{1}|=...=|A_{p-1}|=\frac{|A|-2}{p}=\frac{\dbinom{2p}{p}-2}{p}$$
Nên $|A_{0}|=\frac{\dbinom{2p}{p}-2}{p}+2$

+Nếu $k=2p$ thì $|A_{0}|=1$

+Nếu $k \neq p$ thì $a_{2p-k}=0$ thì tương tự như trên, theo bổ đề ta suy ra
$|A_{0}|=|A_{1}|=...=|A_{p-1}|=\frac{|A|}{p}=\frac{\dbinom{2p}{k}}{p}$
Cuối cùng cho k chạy từ 1 đến 2p thì ta thu được đáp số
 

Bài viết đã được chỉnh sửa nội dung bởi tap lam toan: 19-04-2015 - 08:04