[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Năm 2011, trong đề thi trường THPT Chuyên Nguyễn Huệ, đã có một câu Tổ hợp như sau:
Bài 5:
Chứng minh rằng từ 53 số tự nhiên bất kì luôn chọn được 27 số mà tổng của chúng chia hết cho 27.
Nhìn thoáng qua ta có thể thấy bài này không quá dễ. Đây là cách làm đề xuất:
Ta sử dụng bổ đề: Trong 5 số tự nhiên bất kỳ luôn chọn được 3 số sao cho tổng 3 số chia hết cho 3.
Xét số dư của 5 số tự nhiên khi chia cho 3.
+Nếu có 3 số có cùng số dư khi chia cho 3 thì tổng 3 số đó chia hết cho 3.
+Nếu không có 3 số nào có cùng số dư khi chia cho 3 thì ít nhất tồn tại 1 số chia hết cho 3, 1 số chia 3 dư 1, 1 số chia 3 dư 2 nên tổng 3 số này chia hết cho 3.
Vậy bổ đề được chứng minh.
Tiếp tục chứng minh:
Trong 17 số tự nhiên luôn chọn được 9 số sao cho tổng của 9 số chia hết cho 9.
Áp dụng bổ đề ở trên ta có :
Lấy 3 bộ 5 số ta chọn được 3 bộ số có tổng chia hết cho 3.
Như vậy còn 8 số, lấy tiếp 5 số thì ta chọn được 1 bộ 3 số có tổng chia hết cho 3.
Còn 5 số cuối cùng ta chọn được thêm 1 bộ 3 số có tổng chia hết cho 3.
Do đó ta có 5 bộ 3 số có tổng chia hết cho 3.
Tổng 5 bộ 3 số lần lượt là : [imath]T_1;\ T_2;\ T_3\ T_4;\ T_5[/imath]
Xét 5 số tự nhiên :
[imath]\frac{T_1}{3};\ \frac{T_2}{3};\ \frac{T_3}{3};\ \frac{T_4}{3};\ \frac{T_5}{3}[/imath] thì ta luôn chọn được 3 số chia hết cho 3 do đó tồn tại 3 số trong 5 tổng trên có tổng chia hết cho 9.
Trong 53 số tự nhiên ta chọn được 5 bộ, mỗi bộ gồm 9 số tự nhiên có tổng chia hết cho 9.
Tổng của các bộ số lần lượt là [imath]S_1;\ S_2;\ S_3;\ S_4;\ S_5[/imath]
Xét bộ 5 số tự nhiên [imath]\frac{S_1}{9};\ \frac{S_2}{9};\ \frac{S_3}{9};\ \frac{S_4}{9};\ \frac{S_5}{9}[/imath]áp dụng bổ đề ban đầu thì ta chọn được 3 số sao cho tổng chia hết cho 3 do đó trong 5 số [imath]S_1;\ S_2;\ S_3;\ S_4;\ S_5[/imath] sẽ tồn tại 3 số có tổng chia hết cho 27( điều phải chứng minh)
Nhìn đề bài ta thấy số 27 và 53 được đưa ra không tự nhiên lắm (?) Phải chăng có thể tổng quát được bài này?
"Mệnh đề sau đúng hay sai, và nếu đúng thì hãy chứng minh, nếu sai hãy đưa ra phản chứng:
Trong [imath]2n-1[/imath] số nguyên bất kỳ, luôn tồn tại n số có tổng chia hết cho n."
Câu trả lời là đúng. Và cách chứng minh của chúng ta sẽ dựa vào bổ đề sau:
"Từ n số nguyên bất kỳ ta luôn chọn được 1 số số có tổng chia hết cho n."
Bài toán này đã khá quen thuộc với các bạn lớp 9, và có thể dễ dàng chứng minh bằng nguyên lí Dirichlet.
Chứng minh:
Xét n số [imath]a_1,a_2,...,a_n[/imath]. Thành lập các tổng [imath]S_i=a_1+a_2+...+a_i=[/imath][imath]\sum_{j=1}^{i}a_j[/imath]
Khi đó nếu trong n tổng trên có 1 tổng chia hết cho n thì ta có đpcm. Trường hợp còn lại ta có n tổng và n - 1 số dư từ [imath]1[/imath] đến [imath]n-1[/imath] khi chia cho n nên theo nguyên lí Dirichlet tồn tại 2 tổng [imath]S_i,S_j ( i > j)[/imath] có cùng số dư khi chia n. Khi đó ta chọn [imath]S=S_i-S_j[/imath] sẽ thỏa mãn bài toán.
Quay lại bài toán:
Cách 1:
Để ý rằng trong bài toán này, chúng ta có thể tịnh tiến tất cả các số đi [imath]k[/imath] đơn vị thì tổng n số bất kì luôn giữ nguyên số dư khi chia cho n.
Gọi m là số lớn nhất thỏa mãn rằng có m số đồng dư với nhau theo module n. Nếu [imath]m \geq n[/imath] thì ta chỉ cần chọn n số từ m số đó. Còn nếu [imath]m \leq 2[/imath], 2n - 1 số đã cho có n số dư khi chia cho n, và trong n số dư đó chỉ có 1 số dư xuất hiện 1 lần. Ta xét 2 trường hợp:
+ [imath]n[/imath] lẻ. Khi đó ta chọn n số có số dư khác nhau khi chia cho n.
+ [imath]n \vdots 2[/imath]. Nếu số dư [imath]\frac{n}{2}[/imath] chỉ xuất hiện 1 lần thì ta chọn các số có số dư khi chia cho n là [imath]0,0,1,2,...,\frac{n}{2}-1, \frac{n}{2}+1,...,n-1[/imath]. Còn nếu số dư [imath]\frac{n}{2}[/imath] xuất hiện 2 lần thì ta chọn bộ số có số dư là [imath]1,2,...,\frac{n}{2},\frac{n}{2},\frac{n}{2}+1,...,n-1[/imath]
Với [imath]2<m<n[/imath], ta tịnh tiến 2n - 1 số ban đầu sao cho có m số chia hết cho n. Xét [imath]2n-1-m \geq n[/imath] số còn lại, áp dụng bổ đề trên ta chọn được [imath]h[/imath] số có tổng chia hết cho n.
Nếu [imath]h+m \geq n[/imath] thì ta chọn [imath]h[/imath] số trên cùng với [imath]n-h \leq m[/imath] số chia hết cho n.
Nếu [imath]k+m<n[/imath] thì xét [imath]2n-1-h-m \geq n[/imath] số còn lại, tiếp tục quá trình trên. Ta thấy quá trình trên phải dùng lại vì các số được xét luôn giảm xuống. Khi quá trình kết thúc thì ta sẽ luôn thu được n số thỏa mãn.(đpcm)
***
Bình luận: Cách trên nhìn sơ qua thì có vẻ dễ, nhưng để nghĩ ra cách này thì người giải cần tốn kha khá thời gian để phân tích, cũng như phải kiên trì để có thể tìm ra được quá trình trên. Đặc biệt, ngoài khái niệm "tịnh tiến số" thì cách trên là một cách thuần THCS. (!)
Tiếp đây là cách thứ 2, có vẻ dài hơn nhưng lại sử dụng ít lập luận, thay vào đó là kiến thức Số học của 11.
Cách 2:
Ta sẽ chứng minh bài toán thông qua 2 ý chính:
1. Bài toán đúng với p là số nguyên tố.
2. Nếu bài toán đúng với 2 số bất kì k, q thì cũng đúng với số k.q.
Khi đó, vì theo phân tích của n là [imath]p_1^{\alpha_1}.p_2^{\alpha_2}...p_i^{\alpha_i}.[/imath] nên bằng quy nạp ta có thể thấy bài toán đúng với n là số tự nhiên.
+ Bài toán đúng với p là số nguyên tố.
Đặt [imath]S(X)[/imath] là tổng của các phần tử thuộc tập hợp X bất kỳ. Giả sử tồn tại 1 tập hợp S có 2p - 1 số nguyên sao cho tổng p số bất kỳ không chia hết cho p.
Khi đó [imath]\forall A\subset S,|A|=p: S(A)\not\equiv 0(modp)\Rightarrow [S(A)]^{p-1}\equiv 1(modp)[/imath] theo định lý nhỏ Fermat.
[imath]\Rightarrow S'=\sum_{A \subset S,|A|=p}[S(A)]^{p-1}\equiv C_{2p-1}^p\not\equiv 0(modp)[/imath]
Xét tập [imath]A_i[/imath] có p phần tử [imath]a_{i_1},a_{i_2},...,a_{i_p}[/imath]
[imath][S(A_i)]^{p-1}=(a_{i_1}+a_{i_2}+...+a_{i_p})^{p-1}=\sum _{\alpha}\frac{(p-1)!}{\alpha _1!\alpha _2!...\alpha _p!}\prod _{j=1}^{p}a_{i_j}^{\alpha _j}[/imath]
(với [imath]\alpha[/imath] là 1 bộ [imath]\alpha _1,\alpha _2,...,\alpha _p[/imath] nguyên không âm bất kỳ sao cho [imath]\alpha _1+\alpha _2+...+\alpha _p=p-1[/imath])
Cố định bộ [imath]\alpha[/imath], xét [imath]T=\sum _{(a_{i_1},a_{i_2},...,a_{i_p})}\prod _{j=1}^{p}a_{i_j}^{\alpha _j}[/imath]
Các phần tử [imath]a_{i_j}[/imath] có thể quy đổi thành 1 đơn ánh đi từ [imath]\left \{ 1,2,...,p \right \}\rightarrow \left \{ 1,2,...,2p-1 \right \}[/imath].
Xét bộ [imath]\alpha[/imath]. Giả sử trong bộ có [imath]m \leq p[/imath] phần tử dương. Khi đó trong tổng T, khi hoán vị [imath]a_{i_j}[/imath] thì giá trị của [imath]m[/imath] phần tử mới thay đổi, các phần tử bằng 0 khi ở số mũ thì giá trị lũy thừa luôn bằng 1. Cho nên ta chỉ xét m phần tử đó. Số đơn ánh đi từ [imath]\left \{ 1,2,...,p \right \}\rightarrow \left \{ 1,2,...,2p-1 \right \}[/imath] và có m phần tử trong ánh xạ là [imath]C_{2p-m-1}^{p-m}[/imath]
Cho nên [imath]T \vdots C_{2p-m-1}^{p-m}[/imath]
Mà [imath]C_{2p-m-1}^{p-m}=\frac{(2p-m-1)!}{(p-m)!(p-1)!} \vdots p[/imath] vì tử số chia hết cho p, mẫu số không chia hết cho p và phân thức đó nguyên. Từ đó [imath]T \vdots p, S' \vdots p[/imath](mâu thuẫn)
Vậy ta có đpcm.
+ Nếu bài toán đúng với 2 số bất kì k, q thì cũng đúng với số k.q.
Vì [imath]2kq-1 \geq k(2q-1)[/imath] nên từ [imath]2kq-1[/imath] ban đầu ta chọn được 2q - 1 bộ k số chia hết cho k. Giả sử tổng k bộ đó lần lượt là [imath]x_1,x_2,...,x_{2q-1}[/imath]
Xét 2q - 1 số [imath]\frac{x_1}{k},\frac{x_2}{k},...,\frac{x_{2q-1}}{k}[/imath]. Từ 2q - 1 số này ta chọn được q số có tổng chia hết cho q, giả sử là [imath]\frac{x_{i_1}}{k},\frac{x_{i_2}}{k},...,\frac{x_{i_k}}{k}[/imath] . Khi đó [imath]x_{i_1}+x_{i_2}+...+x_{i_k}\vdots kq[/imath] . Mà tổng đó gồm có [imath]kq[/imath] số nên ta có đpcm.
Vậy bài toán đã được chứng minh.
***
Mọi người ai có ý kiến gì thêm có thể đóng góp vào topic này nhé
Bài 5:
Chứng minh rằng từ 53 số tự nhiên bất kì luôn chọn được 27 số mà tổng của chúng chia hết cho 27.
Nhìn thoáng qua ta có thể thấy bài này không quá dễ. Đây là cách làm đề xuất:
Ta sử dụng bổ đề: Trong 5 số tự nhiên bất kỳ luôn chọn được 3 số sao cho tổng 3 số chia hết cho 3.
Xét số dư của 5 số tự nhiên khi chia cho 3.
+Nếu có 3 số có cùng số dư khi chia cho 3 thì tổng 3 số đó chia hết cho 3.
+Nếu không có 3 số nào có cùng số dư khi chia cho 3 thì ít nhất tồn tại 1 số chia hết cho 3, 1 số chia 3 dư 1, 1 số chia 3 dư 2 nên tổng 3 số này chia hết cho 3.
Vậy bổ đề được chứng minh.
Tiếp tục chứng minh:
Trong 17 số tự nhiên luôn chọn được 9 số sao cho tổng của 9 số chia hết cho 9.
Áp dụng bổ đề ở trên ta có :
Lấy 3 bộ 5 số ta chọn được 3 bộ số có tổng chia hết cho 3.
Như vậy còn 8 số, lấy tiếp 5 số thì ta chọn được 1 bộ 3 số có tổng chia hết cho 3.
Còn 5 số cuối cùng ta chọn được thêm 1 bộ 3 số có tổng chia hết cho 3.
Do đó ta có 5 bộ 3 số có tổng chia hết cho 3.
Tổng 5 bộ 3 số lần lượt là : [imath]T_1;\ T_2;\ T_3\ T_4;\ T_5[/imath]
Xét 5 số tự nhiên :
[imath]\frac{T_1}{3};\ \frac{T_2}{3};\ \frac{T_3}{3};\ \frac{T_4}{3};\ \frac{T_5}{3}[/imath] thì ta luôn chọn được 3 số chia hết cho 3 do đó tồn tại 3 số trong 5 tổng trên có tổng chia hết cho 9.
Trong 53 số tự nhiên ta chọn được 5 bộ, mỗi bộ gồm 9 số tự nhiên có tổng chia hết cho 9.
Tổng của các bộ số lần lượt là [imath]S_1;\ S_2;\ S_3;\ S_4;\ S_5[/imath]
Xét bộ 5 số tự nhiên [imath]\frac{S_1}{9};\ \frac{S_2}{9};\ \frac{S_3}{9};\ \frac{S_4}{9};\ \frac{S_5}{9}[/imath]áp dụng bổ đề ban đầu thì ta chọn được 3 số sao cho tổng chia hết cho 3 do đó trong 5 số [imath]S_1;\ S_2;\ S_3;\ S_4;\ S_5[/imath] sẽ tồn tại 3 số có tổng chia hết cho 27( điều phải chứng minh)
Nhìn đề bài ta thấy số 27 và 53 được đưa ra không tự nhiên lắm (?) Phải chăng có thể tổng quát được bài này?
"Mệnh đề sau đúng hay sai, và nếu đúng thì hãy chứng minh, nếu sai hãy đưa ra phản chứng:
Trong [imath]2n-1[/imath] số nguyên bất kỳ, luôn tồn tại n số có tổng chia hết cho n."
Câu trả lời là đúng. Và cách chứng minh của chúng ta sẽ dựa vào bổ đề sau:
"Từ n số nguyên bất kỳ ta luôn chọn được 1 số số có tổng chia hết cho n."
Bài toán này đã khá quen thuộc với các bạn lớp 9, và có thể dễ dàng chứng minh bằng nguyên lí Dirichlet.
Chứng minh:
Xét n số [imath]a_1,a_2,...,a_n[/imath]. Thành lập các tổng [imath]S_i=a_1+a_2+...+a_i=[/imath][imath]\sum_{j=1}^{i}a_j[/imath]
Khi đó nếu trong n tổng trên có 1 tổng chia hết cho n thì ta có đpcm. Trường hợp còn lại ta có n tổng và n - 1 số dư từ [imath]1[/imath] đến [imath]n-1[/imath] khi chia cho n nên theo nguyên lí Dirichlet tồn tại 2 tổng [imath]S_i,S_j ( i > j)[/imath] có cùng số dư khi chia n. Khi đó ta chọn [imath]S=S_i-S_j[/imath] sẽ thỏa mãn bài toán.
Quay lại bài toán:
Cách 1:
Để ý rằng trong bài toán này, chúng ta có thể tịnh tiến tất cả các số đi [imath]k[/imath] đơn vị thì tổng n số bất kì luôn giữ nguyên số dư khi chia cho n.
Gọi m là số lớn nhất thỏa mãn rằng có m số đồng dư với nhau theo module n. Nếu [imath]m \geq n[/imath] thì ta chỉ cần chọn n số từ m số đó. Còn nếu [imath]m \leq 2[/imath], 2n - 1 số đã cho có n số dư khi chia cho n, và trong n số dư đó chỉ có 1 số dư xuất hiện 1 lần. Ta xét 2 trường hợp:
+ [imath]n[/imath] lẻ. Khi đó ta chọn n số có số dư khác nhau khi chia cho n.
+ [imath]n \vdots 2[/imath]. Nếu số dư [imath]\frac{n}{2}[/imath] chỉ xuất hiện 1 lần thì ta chọn các số có số dư khi chia cho n là [imath]0,0,1,2,...,\frac{n}{2}-1, \frac{n}{2}+1,...,n-1[/imath]. Còn nếu số dư [imath]\frac{n}{2}[/imath] xuất hiện 2 lần thì ta chọn bộ số có số dư là [imath]1,2,...,\frac{n}{2},\frac{n}{2},\frac{n}{2}+1,...,n-1[/imath]
Với [imath]2<m<n[/imath], ta tịnh tiến 2n - 1 số ban đầu sao cho có m số chia hết cho n. Xét [imath]2n-1-m \geq n[/imath] số còn lại, áp dụng bổ đề trên ta chọn được [imath]h[/imath] số có tổng chia hết cho n.
Nếu [imath]h+m \geq n[/imath] thì ta chọn [imath]h[/imath] số trên cùng với [imath]n-h \leq m[/imath] số chia hết cho n.
Nếu [imath]k+m<n[/imath] thì xét [imath]2n-1-h-m \geq n[/imath] số còn lại, tiếp tục quá trình trên. Ta thấy quá trình trên phải dùng lại vì các số được xét luôn giảm xuống. Khi quá trình kết thúc thì ta sẽ luôn thu được n số thỏa mãn.(đpcm)
***
Bình luận: Cách trên nhìn sơ qua thì có vẻ dễ, nhưng để nghĩ ra cách này thì người giải cần tốn kha khá thời gian để phân tích, cũng như phải kiên trì để có thể tìm ra được quá trình trên. Đặc biệt, ngoài khái niệm "tịnh tiến số" thì cách trên là một cách thuần THCS. (!)
Tiếp đây là cách thứ 2, có vẻ dài hơn nhưng lại sử dụng ít lập luận, thay vào đó là kiến thức Số học của 11.
Cách 2:
Ta sẽ chứng minh bài toán thông qua 2 ý chính:
1. Bài toán đúng với p là số nguyên tố.
2. Nếu bài toán đúng với 2 số bất kì k, q thì cũng đúng với số k.q.
Khi đó, vì theo phân tích của n là [imath]p_1^{\alpha_1}.p_2^{\alpha_2}...p_i^{\alpha_i}.[/imath] nên bằng quy nạp ta có thể thấy bài toán đúng với n là số tự nhiên.
+ Bài toán đúng với p là số nguyên tố.
Đặt [imath]S(X)[/imath] là tổng của các phần tử thuộc tập hợp X bất kỳ. Giả sử tồn tại 1 tập hợp S có 2p - 1 số nguyên sao cho tổng p số bất kỳ không chia hết cho p.
Khi đó [imath]\forall A\subset S,|A|=p: S(A)\not\equiv 0(modp)\Rightarrow [S(A)]^{p-1}\equiv 1(modp)[/imath] theo định lý nhỏ Fermat.
[imath]\Rightarrow S'=\sum_{A \subset S,|A|=p}[S(A)]^{p-1}\equiv C_{2p-1}^p\not\equiv 0(modp)[/imath]
Xét tập [imath]A_i[/imath] có p phần tử [imath]a_{i_1},a_{i_2},...,a_{i_p}[/imath]
[imath][S(A_i)]^{p-1}=(a_{i_1}+a_{i_2}+...+a_{i_p})^{p-1}=\sum _{\alpha}\frac{(p-1)!}{\alpha _1!\alpha _2!...\alpha _p!}\prod _{j=1}^{p}a_{i_j}^{\alpha _j}[/imath]
(với [imath]\alpha[/imath] là 1 bộ [imath]\alpha _1,\alpha _2,...,\alpha _p[/imath] nguyên không âm bất kỳ sao cho [imath]\alpha _1+\alpha _2+...+\alpha _p=p-1[/imath])
Cố định bộ [imath]\alpha[/imath], xét [imath]T=\sum _{(a_{i_1},a_{i_2},...,a_{i_p})}\prod _{j=1}^{p}a_{i_j}^{\alpha _j}[/imath]
Các phần tử [imath]a_{i_j}[/imath] có thể quy đổi thành 1 đơn ánh đi từ [imath]\left \{ 1,2,...,p \right \}\rightarrow \left \{ 1,2,...,2p-1 \right \}[/imath].
Xét bộ [imath]\alpha[/imath]. Giả sử trong bộ có [imath]m \leq p[/imath] phần tử dương. Khi đó trong tổng T, khi hoán vị [imath]a_{i_j}[/imath] thì giá trị của [imath]m[/imath] phần tử mới thay đổi, các phần tử bằng 0 khi ở số mũ thì giá trị lũy thừa luôn bằng 1. Cho nên ta chỉ xét m phần tử đó. Số đơn ánh đi từ [imath]\left \{ 1,2,...,p \right \}\rightarrow \left \{ 1,2,...,2p-1 \right \}[/imath] và có m phần tử trong ánh xạ là [imath]C_{2p-m-1}^{p-m}[/imath]
Cho nên [imath]T \vdots C_{2p-m-1}^{p-m}[/imath]
Mà [imath]C_{2p-m-1}^{p-m}=\frac{(2p-m-1)!}{(p-m)!(p-1)!} \vdots p[/imath] vì tử số chia hết cho p, mẫu số không chia hết cho p và phân thức đó nguyên. Từ đó [imath]T \vdots p, S' \vdots p[/imath](mâu thuẫn)
Vậy ta có đpcm.
+ Nếu bài toán đúng với 2 số bất kì k, q thì cũng đúng với số k.q.
Vì [imath]2kq-1 \geq k(2q-1)[/imath] nên từ [imath]2kq-1[/imath] ban đầu ta chọn được 2q - 1 bộ k số chia hết cho k. Giả sử tổng k bộ đó lần lượt là [imath]x_1,x_2,...,x_{2q-1}[/imath]
Xét 2q - 1 số [imath]\frac{x_1}{k},\frac{x_2}{k},...,\frac{x_{2q-1}}{k}[/imath]. Từ 2q - 1 số này ta chọn được q số có tổng chia hết cho q, giả sử là [imath]\frac{x_{i_1}}{k},\frac{x_{i_2}}{k},...,\frac{x_{i_k}}{k}[/imath] . Khi đó [imath]x_{i_1}+x_{i_2}+...+x_{i_k}\vdots kq[/imath] . Mà tổng đó gồm có [imath]kq[/imath] số nên ta có đpcm.
Vậy bài toán đã được chứng minh.
***
Mọi người ai có ý kiến gì thêm có thể đóng góp vào topic này nhé
Last edited:
