Đề bài: Cho 7 số nguyên tùy ý. Chứng minh rằng luôn có thể chọn ra 2 số sao cho tổng hoặc hiệu của chúng chia hết cho 10.
Nếu ta chỉ lập 10 chuồng là 10 số dư khi chia cho 10 ($0, 1, 2, ..., 9$), ta cần tới 11 số (bồ câu) để chắc chắn có 2 số cùng số dư (hiệu chia hết cho 10). Nhưng đề bài chỉ cho 7 số.
Vậy bí quyết ở đây là gì? Ta phải gộp các số dư có tính chất "bù nhau" (tổng chia hết cho 10) vào chung một chuồng!
Bước 1: Thiết kế chuồng thông minh. Một số nguyên khi chia cho 10 sẽ có các số dư từ 0 đến 9. Ta nhóm các số dư này thành 6 cái chuồng như sau:
Chuồng 0: Các số chia 10 dư 0
Chuồng 1: Các số chia 10 dư 1 hoặc dư 9 (Vì $1 + 9 = 10$)
Chuồng 2: Các số chia 10 dư 2 hoặc dư 8 (Vì $2 + 8 = 10$)
Chuồng 3: Các số chia 10 dư 3 hoặc dư 7 (Vì $3 + 7 = 10$)
Chuồng 4: Các số chia 10 dư 4 hoặc dư 6 (Vì $4 + 6 = 10$)
Chuồng 5: Các số chia 10 dư 5
Bước 2: Áp dụng Dirichlet.
Coi 7 số nguyên đã cho là 7 con bồ câu nhốt vào 6 cái chuồng số dư ở trên. Vì $7 > 6$, theo nguyên lý Dirichlet, chắc chắn có ít nhất 2 số lọt vào cùng một chuồng.
Bước 3: Biện luận kết quả.
Xét 2 số cùng nằm trong một chuồng, sẽ có 2 trường hợp xảy ra:
Trường hợp lẻ: Chúng có cùng số dư (ví dụ cùng dư 3, hoặc cùng dư 7). Lúc này, hiệu của chúng sẽ chia hết cho 10.
Trường hợp chẵn: Chúng có số dư khác nhau nhưng tổng bằng 10 (ví dụ một số dư 3, một số dư 7). Lúc này, tổng của chúng sẽ chia hết cho 10.
Kết luận: Trong mọi trường hợp, luôn chọn được 2 số có tổng hoặc hiệu chia hết cho 10 (Đpcm).
Đề bài: Chứng minh rằng từ $n+1$ số nguyên bất kỳ ($n \ge 1$), luôn có thể chọn ra 2 số sao cho hiệu của chúng chia hết cho $n$.
Đây là bài toán tổng quát hóa của bài toán chia hết cho 5 ở module trước. Con cần làm quen với việc lập luận bằng biến số $n$ thay vì các con số cụ thể.
Xây chuồng: Khi chia một số nguyên bất kỳ cho $n$, số dư chỉ có thể là một trong $n$ giá trị: $0, 1, 2, ..., n-1$. Ta lập $n$ cái chuồng tương ứng với $n$ số dư này.
Bồ câu: Đề bài cho $n+1$ số nguyên, ta coi đây là $n+1$ con bồ câu.
Áp dụng Dirichlet: Nhốt $n+1$ con bồ câu vào $n$ cái chuồng số dư. Vì $n+1 > n$, theo nguyên lý Dirichlet, luôn tồn tại ít nhất 2 số nguyên có cùng số dư khi chia cho $n$.
Gọi 2 số đó là $a$ và $b$ ($a > b$). Vì $a$ và $b$ có cùng số dư khi chia cho $n$ nên ta có thể viết:
$a = n \cdot q_1 + r$
$b = n \cdot q_2 + r$ (với $0 \le r < n$)
$\implies a - b = n(q_1 - q_2) \ \vdots \ n$.
Kết luận: Hiệu của 2 số này chắc chắn chia hết cho $n$ (Đpcm).
Đề bài: Cho một dãy gồm 10 số nguyên dương bất kỳ: $a_1, a_2, a_3, ..., a_{10}$. Chứng minh rằng luôn tồn tại một vài số hạng đứng liên tiếp nhau trong dãy sao cho tổng của chúng chia hết cho 10.
(Ví dụ: dãy gồm một số hạng, hoặc tổng $a_2 + a_3 + a_4 \ \vdots \ 10$).
Bài toán này rất khó nếu con cố gắng đi ghép cặp ngẫu nhiên. Bí quyết của dạng toán "tổng liên tiếp" này là Thiết lập dãy tổng tích lũy (Tổng dồn). Đây là kỹ thuật cực kỳ mạnh trong toán rời rạc.
Bước 1: Thiết lập các tổng dồn.
Ta đặt các tổng từ đầu dãy đến vị trí thứ $i$ như sau:
$S_1 = a_1$
$S_2 = a_1 + a_2$
$S_3 = a_1 + a_2 + a_3$
...
$S_{10} = a_1 + a_2 + a_3 + ... + a_{10}$
Ta có tất cả 10 tổng dồn từ $S_1$ đến $S_{10}$.
Bước 2: Xét các số dư khi chia cho 10.
Mang 10 tổng này đi chia cho 10. Sẽ có 2 kịch bản xảy ra:
Kịch bản 1: Nếu có một tổng $S_k$ nào đó chia hết cho 10. Bài toán được giải quyết ngay lập tức (Tổng các số liên tiếp từ $a_1$ đến $a_k$ chính là tổng cần tìm).
Kịch bản 2: Nếu không có tổng nào trong 10 tổng trên chia hết cho 10. Nghĩa là khi chia cho 10, các tổng này chỉ được phép nhận 9 loại số dư: từ $1$ đến $9$.
Bước 3: Ép vào chuồng Dirichlet.
Coi 10 tổng dồn ($S_1 \rightarrow S_{10}$) là 10 con bồ câu.
Coi 9 loại số dư (từ 1 đến 9) là 9 cái chuồng.
Theo nguyên lý Dirichlet, vì $10 > 9$, nên chắc chắn tồn tại ít nhất 2 tổng dồn có cùng số dư khi chia cho 10. Giả sử đó là $S_i$ và $S_j$ ($1 \le i < j \le 10$).
Bước 4: Chốt hạ.
Vì $S_i$ và $S_j$ có cùng số dư khi chia cho 10, nên hiệu của chúng phải chia hết cho 10:
$S_j - S_i \ \vdots \ 10$
$\implies (a_1 + a_2 + ... + a_j) - (a_1 + a_2 + ... + a_i) \ \vdots \ 10$
$\implies a_{i+1} + a_{i+2} + ... + a_j \ \vdots \ 10$.
Rõ ràng đây chính là tổng của các số hạng đứng liên tiếp nhau trong dãy (từ vị trí $i+1$ đến $j$). Bài toán được chứng minh hoàn toàn!