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

[anh qua]

Cho $n,m,k,t$ là các số nguyên dương thảo mãn $ n\geq m \geq k$ và  $ n +{} m -{} k +{} 1={} 2^t$. Chứng minh rằng.

$ {m \choose k} +{} {n \choose k}$ là số chẵn

Bài viết đã được chỉnh sửa nội dung bởi anh qua: 31-03-2013 - 10:25

[Karl Heinrich Marx]

Cho $n,m,k,t$ là các số nguyên dương thảo mãn $ n\geq m \geq k$ và  $ n +{} m -{} k +{} 1={} 2^t$. Chứng minh rằng.

$ {m \choose k} +{} {n \choose k}$ là số chẵn

Dùng định lí Lucas, xét biểu diễn nhị phân của 3 số m,n,k. 

Đặt $m= \sum\limits_{i=1}^{N}m_i2^i,n=\sum\limits_{i=1}^{N}n_i2^i,k=\sum\limits_{i=1}^{N}k_i2^i$ với $N$ đủ lớn.

Nếu với mỗi $i$ mà $n_i,m_i \ge k_i$ hoặc $n_i,m_i \le k_i$ thì $C_{n}^k$ và $C_{m}^k$ cùng tính chẵn lẻ nên tổng chẵn.

Nếu tồn tại $j$ mà $1=n_j=k_j>m_j=0$ (trường hợp $m_j=k_j>n_j=0$ tương tự)

ta thấy $m+n-k=2^t-1= \sum\limits_{i=1}^{t-1}2^i$

Dễ thấy rằng $j<t-1$ mặt khác trong biểu diễn nhị phân của $m+n-k$ thì vì $1=n_j=k_j>m_j=0$ nên hệ số của $2^{j}$ và $2^{j-1}$ có ít nhất 1 số bằng 0. Mâu thuẫn,

Bài viết đã được chỉnh sửa nội dung bởi Karl Heinrich Marx: 01-04-2013 - 11:26

[nguyenta98]

Cho $n,m,k,t$ là các số nguyên dương thảo mãn $ n\geq m \geq k$ và  $ n +{} m -{} k +{} 1={} 2^t$. Chứng minh rằng.

$ {m \choose k} +{} {n \choose k}$ là số chẵn

Em có một cách không dùng định lý Lucas, đại ca Karl xem giúp em nhé

Giải như sau:

Giả sử phản chứng $\binom{m}{k}+\binom{n}{k}$ lẻ khi ấy không mtq, giả sử $\binom{m}{k}$ lẻ

Xét $\binom{m}{k}=\dfrac{m!}{(m-k)!.k!}$
Ta có $v_2(m!)=\sum_{i=1}^{\infty}\left\lfloor\dfrac{m}{p^i}\right\rfloor$

$v_2((m-k)!.k!)=\sum_{i=1}^{\infty}\left(\left\lfloor\dfrac{m-k}{p^i}\right\rfloor+\left\lfloor\dfrac{k}{p^i}\right\rfloor\right)$

Mà $\binom{m}{k}$ lẻ nên $\sum_{i=1}^{\infty}\left\lfloor\dfrac{m}{p^i}\right\rfloor=\sum_{i=1}^{\infty}\left(\left\lfloor\dfrac{m-k}{p^i}\right\rfloor+\left\lfloor\dfrac{k}{p^i}\right\rfloor\right)$ mặt khác áp dụng BDT $[x+y]\geq [x]+[y]$ thì $VT\geq VP$ mà để dấu $=$ xảy ra thì buộc $\left\lfloor\dfrac{m}{p^i}\right\rfloor=\left\lfloor\dfrac{m-k}{p^i}\right\rfloor+\left\lfloor\dfrac{k}{p^i}\right\rfloor$

Muốn như vậy thì $m=2^i.u+v,k=2^i.x+y$ thì $v\geq y$ $(1)$

Do $m,n\geq k \Rightarrow m-k+1\geq 1$ nên $n<2^t$ tương tự $m<2^t$ từ đó $k<2^t$
Gọi phân tích dạng nhị phân của hai 3 số là
$m=a_t.2^t+...+a_1.2+a_0$
$n=b_t.2^t+...+b_1.2+b_0$
$k=c_t.2^t+...+c_1.2+c_0$

Với $0\le a_i,b_i,c_i\le 1$

Mặt khác từ $(1)$ $v\geq y$ với $v,y$ là số dư của $m,k$ khi chia cho $2^i$ và từ cách biểu diễn nhị phân ở trên ta dẫn đến ngay

$a_l.2^l+a_{l-1}.2^{l-1}+...+a_1.2+a_0\geq c_l.2^l+c_{l-1}.2^{l-1}+...+c_1.2+c_0$

Từ đó ta dẫn đến ngay rằng $a_j\geq c_j$ với mọi $j$ thật vậy nếu $c_j>a_j$ thì $c_j=1,a_j=0$ khi ấy $a_j.2^j+...+a_1.2+a_0=a_{j-1}.2^{j-1}+...+a_1.2+a_0\le 2^{j-1}+...+2+1=2^{j}-1<c_j.2^j\le c_l.2^l+c_{l-1}.2^{l-1}+...+c_1.2+c_0$ mâu thuẫn

Như vậy $a_j\geq c_j$ với mọi $j$

Và mặt khác $\binom{n}{k}$ chẵn nên lập luận ngược với trên ắt phải tồn tại $b_j<c_j$

Khi ấy $0\le a_j+b_j-c_j<a_j\le 1$ $(2)$

Mặt khác $m+n-k+1=2^t \Rightarrow (a_t+b_t-c_t).2^t+...+(a_1+b_1-c_1).2+(a_0+b_0-c_0)=2^t-1=2^{t-1}+...+2+1$
Nên $a_i+b_i-c_i=1$ với mọi $i$ $(3)$

Từ $(2)(3)$ mâu thuẫn suy ra giả sử phản chứng sai nên có $đpcm$

Bài viết đã được chỉnh sửa nội dung bởi nguyenta98: 01-04-2013 - 22:55

[Karl Heinrich Marx]

2 lời giải này thực chất gần như nhau thôi em ạ.