chứng minh rằng: [tex]2^{2018}-1[/tex] số ngyên bất kì có thể tìm được [tex]2^{2017}[/tex] số mà tổng của chúng chia hết cho [tex]2^{2017}[/tex]
có thể c/m = quy nạp với n = 2, 4, 8, 16, 32, 64, ..., [tex]2^{k}[/tex]
- Với n = 2, xét 3 số nguyên bất kì a1, a2, a3
3 số chia cho 2 thì các số dư chỉ là 0 và 1, nên theo nguyên lý Dirichlê tồn tại 2 số có cùng số dư, do đó tổng 2 số này luôn chia hết cho 2. Vậy khẳng định đúng với n = 2.
- Với n = 4 ta xét 7 số nguyên bất kì a1, a2, ..., a7. Cần c/m rằng trong 7 số nguyên bất kì tồn tại 4 số có tổng chia hết cho 4.
Ta chia 7 số nguyên này thành 3 phần gồm 2 dãy 3 số và thừa ra 1 số. chẳng hạn (a1, a2, a3) và (a4, a5, a6) và a7.
Trong bộ (a1, a2, a3) tồn tại 2 số có tổng chia hết cho 2, giả sử a1 + a2 = 2m.
tương tự với bộ kia, giả sử a4 + a5 = 2p.
Ta còn lại a3, a6 và a7 cũng là 3 số nên cũng tồn tại 2 số có tổng chia hết cho 2, giả sử a6 + a7 = 2q
Suy ra: a1 + a2 + a4 + a5 + a6 + a7 = 2(m + p + q)
m, p, q là 3 số nên tồn tại 2 số có tổng chia hết cho 2, giả sử m + p = 2s.
Suy ra: a1 + a2 + a4 + a5 = 2(m + p) = 4s nên chia hết cho 4. Vậy đúng với n = 4.
- Hoàn toàn tương tự với n = [tex]2^{k}[/tex] ta cần c/m trong [tex]2^{k+1} - 1[/tex] số nguyên bất kì luôn tồn tại [tex]2^{k}[/tex] số có tổng chia hết cho [tex]2^{k}[/tex]
Ta cũng chia làm các phần gồm 2 dãy mỗi dãy có [tex]2^{k} - 1[/tex] số và thừa ra 1 số.
mỗi dãy trên tồn tại [tex]2^{k-1}[/tex] số có tổng chia hết cho [tex]2^{k-1}[/tex], các số còn lại và số thừa ra trên lập thành bộ [tex]2^{k} - 1[/tex] số nên tồn tại [tex]2^{k-1}[/tex] số có tổng chia hết cho [tex]2^{k-1}[/tex]
lý luận tương tự trên ta suy ra đúng với n = [tex]2^{k}[/tex]
Do đó đúng với mọi n = [tex]2^{k}[/tex]
[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
