Bài tổ hợp đa thức mở rộng IMO 1995

[TrauBo]

$\fbox{Bài toán:}$ Cho $p$ nguyên tố lẻ và số nguyên dương $n>2p$. Tìm số các tập con $X$ của $M=\{1,2...,n\}$. biết X chứa đúng $2p$ phần tử và tổng các phần tử của $X$ chia hết cho $p$.

TrauBo ra $\displaystyle \prod_{i=1}^n (x-\epsilon ^ i) = (x^p-1)^k. \prod_{j=1}^r (x-\epsilon^j)$ rồi không biết khai triển VP sao nữa

Ở đây $\epsilon=\cos \dfrac{2\pi}{p}+i\sin \dfrac{2\pi}{p}$ và $n=kp+r$.

Cảm ơn các bạn.
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[conami]

Nguyên văn bởi TrauBo

$\fbox{Bài toán:}$ Cho $p$ nguyên tố lẻ và số nguyên dương $n>2p$. Tìm số các tập con $X$ của $M=\{1,2...,n\}$. biết X chứa đúng $2p$ phần tử và tổng các phần tử của $X$ chia hết cho $p$.

TrauBo ra $\displaystyle \prod_{i=1}^n (x-\epsilon ^ i) = (x^p-1)^k. \prod_{j=1}^r (x-\epsilon^j)$ rồi không biết khai triển VP sao nữa

Ở đây $\epsilon=\cos \dfrac{2\pi}{p}+i\sin \dfrac{2\pi}{p}$ và $n=kp+r$.

Cảm ơn các bạn.

Biến đổi đến đó là ổn rồi bạn ạ
Đến đây so sánh hệ số của $x^{n-2p}$ thì hệ số của vế phải là $C^{2}_{k}$ do $n=kp+r$
$\Rightarrow n-2p = (k-2)p+r$
Ta có
$(x^p-1)^k. \prod_{j=1}^r (x-\epsilon^j)= (x^p-1)^k. (x-\epsilon^1) (x-\epsilon^2)… (x-\epsilon^r)$
Trong khai triển của $(x^p-1)^k$, các số mũ của $x$ là $0,p,2p,…kp$
Và lưu ý là $r<p$ cho nên hệ số của $x^{(k-2)p+r}$ trong khai triển $(x^p-1)^k. \prod_{j=1}^r (x-\epsilon^j)$ chính bằng hệ số của $x^{(k-2)p}$ trong khai triển $(x^p-1)^k$ và bằng $C^{2}_{k}$.

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[cloner]

Nguyên văn bởi conami

Biến đổi đến đó là ổn rồi bạn ạ
Đến đây so sánh hệ số của $x^{n-2p}$ thì hệ số của vế phải là $C^{2}_{k}$ do $n=kp+r$
$\Rightarrow n-2p = (k-2)p+r$
Ta có
$(x^p-1)^k. \prod_{j=1}^r (x-\epsilon^j)= (x^p-1)^k. (x-\epsilon^1) (x-\epsilon^2)… (x-\epsilon^r)$
Trong khai triển của $(x^p-1)^k$, các số mũ của $x$ là $0,p,2p,…kp$
Và lưu ý là $r<p$ cho nên hệ số của $x^{(k-2)p+r}$ trong khai triển $(x^p-1)^k. \prod_{j=1}^r (x-\epsilon^j)$ chính bằng hệ số của $x^{(k-2)p}$ trong khai triển $(x^p-1)^k$ và bằng $C^{2}_{k}$.

Cho mình hỏi sau đoạn này thì làm tiếp như sau có đúng không (do mình mới biết đến kĩ thuật giải toán này nên còn lóng ngóng lắm)

Gọi $a_k $ là số tập con có 2p phần tử của tập M sao cho tổng 2p phần tử này khi chia cho p thì có số dư là k.
Như vậy ta có $(a_0-C_k^2)\epsilon^0+a_1\epsilon^1+...+a_{p-1}\epsilon^{p-1}=0 $
Suy ra đa thức $P(x)=(a_0-C_k^2)x^0+a_1x^1+...+a_{p-1}x^{p-1}=0 $ có $\epsilon $ là nghiệm, nên nó chia hết cho đa thức $Q(x)=x^0+x^1+...+x^{p-1} $ (do Q(x) có $\epsilon $ là nghiệm và là đa thức bất khả quy), do $deg P(x)=deg Q(x) $ nên $P(x)\equiv Q(x) $ nên suy ra $a_0-C_k^2=a_1=a_2=...=a_{p-1} $, mà ta lại có $a_0+a_1+...+a_{p-1}=C_n^{2p} $ do đây là tổng số cách chọn 2p phần tử từ n phần tử của tập M. Từ đó tính được $a_0 $

[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT] 

[TrauBo]

Nguyên văn bởi cloner

Cho mình hỏi sau đoạn này thì làm tiếp như sau có đúng không (do mình mới biết đến kĩ thuật giải toán này nên còn lóng ngóng lắm)

Gọi $a_k $ là số tập con có 2p phần tử của tập M sao cho tổng 2p phần tử này khi chia cho p thì có số dư là k.
Như vậy ta có $(a_0-C_k^2)\epsilon^0+a_1\epsilon^1+...+a_{p-1}\epsilon^{p-1}=0 $
Suy ra đa thức $P(x)=(a_0-C_k^2)x^0+a_1x^1+...+a_{p-1}x^{p-1}=0 $ có $\epsilon $ là nghiệm, nên nó chia hết cho đa thức $Q(x)=x^0+x^1+...+x^{p-1} $ (do Q(x) có $\epsilon $ là nghiệm và là đa thức bất khả quy), do $deg P(x)=deg Q(x) $ nên $P(x)\equiv Q(x) $ nên suy ra $a_0-C_k^2=a_1=a_2=...=a_{p-1} $, mà ta lại có $a_0+a_1+...+a_{p-1}=C_n^{2p} $ do đây là tổng số cách chọn 2p phần tử từ n phần tử của tập M. Từ đó tính được $a_0 $

Bạn làm đúng rồi Đáp số của bài toán là $\dfrac{C_{n}^{2p} - C_k^2}{p}+C_k^2$
[RIGHT][I][B]Nguồn: MathScope.ORG[/B][/I][/RIGHT]