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

[Ego]

Một bài cũ.
Chứng minh rằng $\dbinom{2n}{n}$ chia hết $\text{lcm}(1, 2, \cdots, 2n)$

[Zaraki]

Định lý Kummer sẽ giải sẽ giải quyết bài toán này.

 

Lời giải. Xét một ước nguyên tố $p < 2n$ bất kì, khi đó nếu $p^x<n<p^{x+1}$ thì $n= (\overline{a_xa_{x-1} \cdots a_1a_0})_p$ trong hệ cơ số $p$. Khi đó $v_p \left( \binom{2n}{n} \right)$ chính là số lần nhớ trong phép trùe $2n-n$ trong hệ cơ số $p$. Ta xét hai trường hợp:

 

TH1. Nếu $2p>2a_x>p$ thì khi đó $p^{x+1}<2n<p^{x+2}$ nên $2n= \left( \overline{b_{x+1}b_xb_{x-1} \cdots b_1b_0} \right)_p$ suy ra trong phép trừ $2n$ cho $n$ ở hệ cơ số $p$ thì sẽ có tối đa $x+1$ lần nhớ, do đó $$v_p \left( \binom{2n}{n} \right) \le x+1 = v_p \left( \text{lcm} (1,2, \cdots , 2n) \right).$$

 

TH2. Nếu $2a_x=p-1$ và khi nhân $2$ cho $n= \left( \overline{a_xa_{x-1} \cdots a_1a_0} \right)_p$ thì sẽ có một nhớ từ $a_{x-1}$ chuyển sang $a_x$, khi đó $2n= \left( \overline{10b_{x-1} \cdots b_1b_0} \right)_p$. Trường hợp này cũng sẽ có tối đa $x$ nhớ nên $$v_p \left( \binom{2n}{n} \right) \le x < x+1= v_p \left( \text{lcm} (1,2, \cdots , 2n) \right).$$

 

TH3. Nếu $2a_x \le p-1$ nhưng khi nhân $2$ cho $n$ thì không có nhớ nào từ $a_{x-1}$ chuyển sang, khi đó $p^x<2n<p^{x+1}$ nên $v_p \left( \text{lcm} (1,2, \cdots , 2n) \right) = x$ và $2n= \left( \overline{(2a_x)b_{x-1} \cdots b_1b_0} \right)_p$. Như vậy ta cần chứng minh $v_p \left( \binom{2n}{n} \right) \le x$. Thật vậy, ta chỉ cần để ý rằng sẽ không có nhớ nào khi trừ hệ cơ số thứ $x+1$ của $2n$ (tức $2a_x$) cho hệ cơ số thứ $x+1$ của $n$ (tức $a_x$), do đó số lần nhớ sẽ chỉ tối đa là $x$, hay $v_p \left( \binom{2n}{n} \right) \le x$.

 

Như vậy trong mọi trường hợp, với số nguyên tố $p<2n$ bất kì thì ta luôn có $$v_p \left( \binom{2n}{n} \right) \le v_p \left( \text{lcm} (1,2, \cdots , 2n) \right).$$

Ta suy ra $ \binom{2n}{n}  \mid  \text{lcm} (1,2, \cdots , 2n)$.   $\blacksquare$

Bài viết đã được chỉnh sửa nội dung bởi Zaraki: 20-03-2016 - 11:32

[Visitor]

Bài này số mũ bt cũng ra nhưng chắc dài. cho mình xin tài liệu về $Kummer$ đc ko Jinbe. Trước t cũng có của viện toán nhưng lại chả nhớ để đâu

[Chris yang]

Mượn ý tưởng xét khoảng giá trị $n$ của Zaraki.

 

Gọi $p$ là số nguyên tố bất kỳ

Trước tiên, có: $v_p(\text{lcm}(1,2,...,2n))=\text{max}(v_p(1),....,v_p(2n))=v_p(k)=t$ với $k=\overline{1,2,...,2n}$. Dễ thấy rằng $2n<p^{t+1}$, vì nếu $2n>p^{t+1}$ thì chắc chắn tồn tại $i\in\overline{1,...,n}$ mà $v_p(i)=t+1$ ( vô lý) ($\star$)

Bây giờ cần chứng minh $t+2v_p(n!)\geq v_p((2n)!)$

Từ ($\star$) , áp dụng định lý Legendre về số mũta có $v_p(n!)=\sum ^{t}_{i=1}\left \lfloor \frac{n}{p^i} \right \rfloor;v_p((2n)!)=\sum ^{t}_{i=1}\left \lfloor \frac{2n}{p^i} \right \rfloor$

kết hợp với bổ đề quen thuộc là $\left \lfloor a \right \rfloor+\left \lfloor a+\frac{1}{2} \right \rfloor=\left \lfloor 2a \right \rfloor$ thì  cần có $t+\sum ^{t }_{i=1}\left \lfloor \frac{n}{p^i} \right \rfloor\leq \sum ^{i}_{i=1}\left \lfloor \frac{n}{p_i}+\frac{1}{2} \right \rfloor$

$\Leftrightarrow \sum^{t}_{i=1} \left ( \left \lfloor \frac{n}{p^i}+\frac{1}{2} \right \rfloor-\left \lfloor \frac{n}{p^i} \right \rfloor \right)\leq t$

BĐT này hiển nhiên đúng vì vế trái là tổng của $t$ số hạng, mỗi số hạng đều không vượt quá $1$

Do đó ta có đpcm

 

_______________________________________________

P.s: Đặt gạch hóng xin tài liệu định lý Kummer với. Mình k biết nó là cái gì   

 

[Zaraki]

Bài này số mũ bt cũng ra nhưng chắc dài. cho mình xin tài liệu về $Kummer$ đc ko Jinbe. Trước t cũng có của viện toán nhưng lại chả nhớ để đâu

 

_______________________________________________

P.s: Đặt gạch hóng xin tài liệu định lý Kummer với. Mình k biết nó là cái gì   

 

Xin lỗi vì trả lời các bạn muộn. Quả thật mình không có tài liệu nào vì định lý Kummer này,   mình thấy không có ai viết về cái này đến mức chi tiết có áp dụng cả (các bài áp dụng cũng ít, mình nghĩ thế). 

 

Chỉ là đang lúc đọc cuốn A path to Combinatorics, ông Titu có giới thiệu định lý Kummer và Lucas kèm theo chứng minh, cộng thêm đó là MỘT (chỉ một) bài toán áp dụng định lý Kummer.   Để mình trích dẫn bài đó cho hai bạn thử sức:

 

Bài toán. Xác định tất cả các số nguyên dương $k$ thoả mãn tính chất: Tồn tại số nguyên dương $n >1$ ($n$ phụ thuộc vào $k$) sao cho $\binom nk$ chia hết cho $k$ với mọi $1 \le i \le n-1$.

 

Còn đây là định lý Kummer cho ngocanh99:

 

Định lý Kummer. Cho $n$ và $i$ là hai số nguyên dương với $i \le n$, và cho $p$ là một số nguyên tố. Thì khi đó $\nu_p \binom nk$ chính là số lần nhớ trong phép cộng $n-i$ cho $i$ trong hệ cơ số $p$ (hoặc số lần nhớ phép trừ $n$ cho $i$ trong hệ cơ số $p$).