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

[Stranger411]

Cho số nguyên tố $p>3$ và tập hợp $M=\left\{ 1,2,...,p \right\}$. Với mỗi số nguyên $k$ thỏa mãn $1\le k\le p$ ta đặt : ${{E}_{k}}=\left\{ A\subset M:|A|=k \right\}$ và ${{x}_{k}}=\sum\limits_{A\in {{E}_{k}}}{\left( \min A+\max A \right)}$. Chứng minh rằng:
$$\sum\limits_{k=1}^{p-1}{({{x}_{k}}C_{p}^{k})\equiv0(\bmod \,\,{{p}^{3}})}$$

Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 25-07-2012 - 07:43

[perfectstrong]

Lời giải:
Dễ thấy $C_p^k \vdots p, \forall i=\overline{1,p-1}$ với $p$ nguyên tố.
Do đó, ta chỉ cần chứng minh
$$\sum\limits_{k=1}^{p-1}{x_k} \equiv 0 \pmod {p^2}$$
Với một tập $A \in E_k$ thì $\min A \le p-k+1$ và $\max A \ge k$.
Xét trong một $x_k$ bất kì. Gọi $i$ là 1 phần tử của $M$ sao cho $i \le p-k+1$.
Số các tập $A$ trong $E_k$ nhận $i$ là $\min$ là $C_{p-i}^{k-1}$.
\[
\Rightarrow \sum\limits_{A \in E_k } {\min A} = iC_{p - i}^{k - 1}
\]
Tương tự với $\max$, ta cũng có
\[
\sum\limits_{A \in E_k } {\max A} = \sum\limits_{i = k}^p {iC_i^{k - 1} }
\]
Do đó,
\[
\Rightarrow \sum\limits_{k = 1}^{p - 1} {x_k } = \sum\limits_{k = 1}^{p - 1} {\left( {\sum\limits_{i = 1}^{p - k + 1} {iC_{p - i}^{k - 1} } + \sum\limits_{i = k}^p {iC_i^{k - 1} } } \right)} = \sum\limits_{k = 1}^{p - 1} {\sum\limits_{i = 1}^{p - k + 1} {iC_{p - i}^{k - 1} } } + \sum\limits_{k = 1}^{p - 1} {\sum\limits_{i = k}^p {iC_i^{k - 1} } }
\]

Tới đây thì tịt

[Karl Heinrich Marx]

Lời giải:
Dễ thấy $C_p^k \vdots p, \forall i=\overline{1,p-1}$ với $p$ nguyên tố.
Do đó, ta chỉ cần chứng minh
$$\sum\limits_{k=1}^{p-1}{x_k} \equiv 0 \pmod {p^2}$$

Lời giải sai ngay từ đây. Có vẻ như bài này chỉ chứng minh chia hết cho $p^2$ thôi, thử với $p=3$ có vẻ không đúng.
Ta có: $$ \sum\limits_{A \in E_k } {\min A} = \sum\limits_{i=1}^{p-k+1}iC_{p - i}^{k - 1}=\sum\limits_{i=1}^{p}iC_{p - i}^{k - 1}$$
$$\sum\limits_{A \in E_k } {\max A} = \sum\limits_{i = k}^{p} {iC_{i-1}^{k - 1} }=\sum\limits_{i = 1}^p {iC_{i-1}^{k - 1} }$$
Tổng 2 anh này lại thì ra được là
$$ (p+1)\sum\limits_{i=0}^{p-1}C_i^{k-1}=(p+1)C_p^k$$
Rõ ràng là :
$$ \sum\limits_{k=1}^{p-1}(C_p^{k})^2 \vdots p^2$$

[Stranger411]

Có vẻ như bài này chỉ chứng minh chia hết cho $p^2$ thôi, thử với $p=3$ có vẻ không đúng.

Rõ ràng là :
$$ \sum\limits_{k=1}^{p-1}(C_p^{k})^2 \vdots p^2$$

Anh gì đó ơi, bài này có thể quy về chứng minh:
\[\sum\limits_{k=1}^{p-1}{{{\left( C_{p}^{k} \right)}^{2}}\equiv 1(\bmod \,\,{{p}^{3}})}\]
$$\Leftrightarrow \sum\limits_{k=1}^{p-1}{{{\left( \frac{(p-1)!}{k!(p-k)!} \right)}^{2}}\equiv 0(\bmod \,\,\,p)}$$


Với mỗi $k\in \text{ }\!\!\{\!\!\text{ 1}\text{,2},...,\text{ p-1}\}$ đặt ${{a}_{k}}=\frac{(p-1)!}{k!(p-k)!}$
$$ \Leftrightarrow k!.{{a}_{k}}=(p-1)(p-2)...(p-k+1) $$
$$ \Leftrightarrow k.{{a}_{k}}\equiv {{(-1)}^{k-1}}(\bmod \,\,\,p) $$

Đến đây, dùng định lí Willson thôi anh ạ
Mà $p>3$ mà anh

Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 25-07-2012 - 10:11

[Karl Heinrich Marx]

Anh gì đó ơi, bài này có thể quy về chứng minh:
\[\sum\limits_{k=1}^{p-1}{{{\left( C_{p}^{k} \right)}^{2}}\equiv 1(\bmod \,\,{{p}^{3}})}\]
$$\Leftrightarrow \sum\limits_{k=1}^{p-1}{{{\left( \frac{(p-1)!}{k!(p-k)!} \right)}^{2}}\equiv 0(\bmod \,\,\,p)}$$


Với mỗi $k\in \text{ }\!\!\{\!\!\text{ 1}\text{,2},...,\text{ p-1}\}$ đặt ${{a}_{k}}=\frac{(p-1)!}{k!(p-k)!}$
$$\Leftrightarrow $$k!.{{a}_{k}}=(p-1)(p-2)...(p-k+1)$$
$$\Leftrightarrow k.{{a}_{k}}\equiv {{(-1)}^{k-1}}(\bmod \,\,\,p)$$

Đến đây, dùng định lí Willson thôi anh ạ

anh thử với $p=3$ thấy nó không đúng! Mà thực ra theo cách đặt của em thì $ka_k=C_{p-1}^{k-1}$ cái này đâu chắc là đồng dư $(-1)^{k-1}$ mod p đâu.

[The Gunner]

Lời giải sai ngay từ đây. Có vẻ như bài này chỉ chứng minh chia hết cho $p^2$ thôi, thử với $p=3$ có vẻ không đúng.
Ta có: $$ \sum\limits_{A \in E_k } {\min A} = \sum\limits_{i=1}^{p-k+1}iC_{p - i}^{k - 1}=\sum\limits_{i=1}^{p}iC_{p - i}^{k - 1}$$
$$\sum\limits_{A \in E_k } {\max A} = \sum\limits_{i = k}^{p} {iC_{i-1}^{k - 1} }=\sum\limits_{i = 1}^p {iC_{i-1}^{k - 1} }$$
Tổng 2 anh này lại thì ra được là
$$ (p+1)\sum\limits_{i=0}^{p-1}C_i^{k-1}=(p+1)C_p^k$$
Rõ ràng là :
$$ \sum\limits_{k=1}^{p-1}(C_p^{k})^2 \vdots p^2$$

Ở đầu bài toán có đk là p>3
mình sẽ tiếp tục lời giải của bạn để chứng minh chia hết cho $p^3$
ta có $\sum_{k=1}^{p-1}\binom{p}{k}^2=\binom{2p}{p}-2$
mà theo định lí Wolstenholme ta có $\binom{2p}{p} \equiv 2 (mod p^3)$
phát biểu Định lí http://chuyentoanpbc...2/06/trang1.jpg

Bài viết đã được chỉnh sửa nội dung bởi The Gunner: 25-07-2012 - 10:09

[Karl Heinrich Marx]

Uh có nhớ đến cái phát biểu 4 nhưng mà chả nhớ rõ là đồng dư $p$ mũ bao nhiêu, phát biểu 4 đấy nghe mấy bác lớp trên bảo có cả chứng minh bằng tổ hợp mới máu :-j Không đọc $p>3$ thử ngay trường hợp này tạch luôn :-s

[Stranger411]

Ở đầu bài toán có đk là p>3
mình sẽ tiếp tục lời giải của bạn để chứng minh chia hết cho $p^3$
ta có $\sum_{k=1}^{p-1}\binom{p}{k}^2=\binom{2p}{p}-2$
mà theo định lí Wolstenholme ta có $\binom{2p}{p} \equiv 2 (mod p^3)$
phát biểu Định lí http://chuyentoanpbc...2/06/trang1.jpg

Em năm nay 12 mà chả biết mấy cái này
Em ko bit đánh giá thế nào nên phải dựa vào cách chứng minh của định lí Willson nên nó hơi dài 1 tí

Ta chứng minh:
$\sum\limits_{k=1}^{p-1}{{{\left( C_{p}^{k} \right)}^{2}}\equiv 1(\bmod \,\,{{p}^{3}})}$ (1)

$\Leftrightarrow \sum\limits_{k=1}^{p-1}{{{\left( \frac{(p-1)!}{k!(p-k)!} \right)}^{2}}\equiv 0(\bmod \,\,\,p)}$ (2)

Với mỗi $k\in \text{ }\!\!\{\!\!\text{ 1}\text{,2},...,\text{ p-1}\}$ đặt ${{a}_{k}}=\frac{(p-1)!}{k!(p-k)!}$
$ \Leftrightarrow k!.{{a}_{k}}=(p-1)(p-2)...(p-k+1) $
$ \Leftrightarrow k.{{a}_{k}}\equiv {{(-1)}^{k-1}}(\bmod \,\,\,p) $ (3)

Xét ${{b}_{k}}=\frac{(p-1)!}{k}$, $\forall k\in \left\{ 1,2,...,p-1 \right\}$.

Theo Định lý Wison ta có $k{{b}_{k}}\equiv (-1)(\bmod \,\,\,p)$. (4)

Từ (3) và (4) ta có :
${{a}_{k}}\equiv {{(-1)}^{k}}{{b}_{k}}(\bmod \,\,p)$ (5)

Do $p$ là số nguyên tố và $k\in \left\{ 1,2,...,p-1 \right\}$ nên tồn tại duy nhất $j\in \left\{ 1,2,...,p-1 \right\}$ sao cho:
$(kj)\equiv 1(\bmod \,\,\,p)$$\Rightarrow $${{(kj)}^{2}}\equiv 1(\bmod \,\,\,p)$.

Khi đó:
$$\sum\limits_{k=1}^{p-1}{{{({{b}_{k}})}^{2}}}=\sum\limits_{k=1}^{p-1}{\left( {{({{b}_{k}})}^{2}}.1 \right)}\equiv \sum\limits_{k=1}^{p-1}{\left( {{({{b}_{k}})}^{2}}.{{(kj)}^{2}} \right)}\equiv \left( (p-1)! \right)\sum\limits_{j=1}^{p-1}{{{j}^{2}}(\bmod \,\,\,p)}$$
Mà
$$\sum\limits_{j=1}^{p-1}{{{j}^{2}}=\frac{p(p-1)(2p-1)}{6}\equiv 0(\bmod \,\,\,p)}$$
nên $\sum\limits_{k=1}^{p-1}{{{({{b}_{k}})}^{2}}}\equiv 0(\bmod \,\,\,p)$ (6)

Từ (5) và (6) suy ra $\sum\limits_{k=1}^{p-1}{{{({{a}_{k}})}^{2}}}\equiv 0(\bmod \,\,\,p)$ hay (2) đúng.

Bài viết đã được chỉnh sửa nội dung bởi Stranger411: 25-07-2012 - 10:33

[tranghieu95]

Đây là đề chọn dội tuyển của Nghệ An 2011-2012