ĐĂNG BÀI NGAY để cùng thảo luận với các CAO THỦ trên mọi miền tổ quốc. Hoàn toàn miễn phí! 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:
"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."
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."
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