Cần chọn ít nhất bao nhiêu số tự nhiên khác nhau để luôn tìm được 24 số có tổng chia hết cho 24
ĐĂ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."
Chứng minh: 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 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: 14 Tháng ba 2022 Reactions: chi254, Timeless time, anbinhf and 20 others
Thêm 1 bài toán mở rộng nữa
"Trong [imath]k+m-1[/imath] số nguyên bất kỳ [imath](1 \leq k \leq m, m \vdots k)[/imath], luôn tồn tại [imath]m[/imath] số có tổng chia hết cho k."
Chứng minh:
Mỗi lần ta có thể chọn được 1 bộ [imath]k[/imath] số có tổng chia hết cho [imath]k[/imath]. Mà [imath](q+1)k-1 \geq qk[/imath] nên ta có thể chọn [imath]q[/imath] bộ như thế. Khi đó ta có [imath]q.k=m[/imath] số có tổng chia hết cho [imath]k[/imath](đpcm). Last edited: 14 Tháng ba 2022 Reactions: chi254, Windeee, Timeless time and 8 others |