Chào các em học sinh lớp 12 yêu quý! Hôm nay, chúng ta sẽ cùng nhau chinh phục một bài toán thú vị trong lĩnh vực Toán rời rạc, một chủ đề rất quan trọng cho các em khi bước vào bậc đại học. Bài toán này có vẻ “hóc búa” nhưng thực ra lại rất đẹp và dựa trên một nguyên lý kinh điển.

Đề bài: Trong một nhóm 101 số nguyên, chứng minh luôn tồn tại hai số có hiệu chia hết cho 100.

Chúng ta sẽ cùng xem xét các lựa chọn và tìm ra lời giải đúng.

—

Phân tích các lựa chọn:

* A. Quy tắc cộng: Quy tắc cộng thường dùng để đếm số cách lựa chọn hoặc kết hợp các đối tượng không giao nhau. Nó không trực tiếp giúp chúng ta chứng minh sự tồn tại của hai số thỏa mãn điều kiện về hiệu chia hết.
* B. Nguyên lý Dirichlet: Nguyên lý Dirichlet, hay còn gọi là nguyên lý chuồng bồ câu, là một công cụ mạnh mẽ để chứng minh sự tồn tại của một đối tượng nào đó khi chúng ta có nhiều đối tượng hơn các “ngăn chứa” có thể có. Nó có vẻ rất phù hợp với bài toán này.
* C. Quy tắc nhân: Quy tắc nhân dùng để đếm số cách thực hiện một chuỗi các lựa chọn liên tiếp. Tương tự như quy tắc cộng, nó không phải là công cụ chính để giải quyết bài toán chứng minh sự tồn tại này.
* D. Quy nạp toán học: Quy nạp toán học thường được sử dụng để chứng minh các mệnh đề đúng với mọi số tự nhiên hoặc trong một phạm vi nhất định. Mặc dù có thể áp dụng trong một số bài toán đếm hoặc chứng minh, nhưng với cấu trúc của bài toán này, nó không phải là phương pháp trực tiếp và hiệu quả nhất.

Dựa trên phân tích sơ bộ, chúng ta thấy Nguyên lý Dirichlet có khả năng cao là đáp án đúng. Bây giờ, chúng ta sẽ đi vào chi tiết để chứng minh.

—

Lời giải chi tiết dựa trên Nguyên lý Dirichlet:

Để chứng minh rằng trong một nhóm 101 số nguyên, luôn tồn tại hai số có hiệu chia hết cho 100, chúng ta sẽ sử dụng Nguyên lý Dirichlet.

Bước 1: Xác định các “con bồ câu” và “chuồng bồ câu”.

* Các “con bồ câu”: Trong bài toán này, 101 số nguyên đã cho chính là các “con bồ câu”. Chúng ta có tổng cộng 101 “con bồ câu”.
* Các “chuồng bồ câu”: Chúng ta cần xác định các “ngăn chứa” (chuồng) sao cho nếu hai “con bồ câu” rơi vào cùng một “chuồng”, thì điều kiện của bài toán sẽ được thỏa mãn.
Điều kiện “hiệu chia hết cho 100” gợi ý chúng ta nên xem xét số dư của các số nguyên khi chia cho 100.
Khi chia một số nguyên bất kỳ cho 100, ta có thể nhận được các số dư từ 0 đến 99.
Vậy, chúng ta có thể định nghĩa 100 “chuồng bồ câu” tương ứng với 100 số dư có thể có khi chia cho 100.
Các chuồng bồ câu sẽ là:
Chuồng 0: Các số nguyên có số dư là 0 khi chia cho 100.
Chuồng 1: Các số nguyên có số dư là 1 khi chia cho 100.
…
Chuồng 99: Các số nguyên có số dư là 99 khi chia cho 100.
Tổng cộng chúng ta có 100 chuồng bồ câu.

Bước 2: Áp dụng Nguyên lý Dirichlet.

Nguyên lý Dirichlet phát biểu rằng: Nếu ta có \( n \) “con bồ câu” và \( m \) “chuồng bồ câu”, với \( n > m \), thì ít nhất một “chuồng” phải chứa nhiều hơn một “con bồ câu”.

Trong trường hợp của chúng ta:
* Số “con bồ câu” \( n = 101 \) (101 số nguyên).
* Số “chuồng bồ câu” \( m = 100 \) (100 số dư có thể có khi chia cho 100).

Vì \( n = 101 > m = 100 \), theo Nguyên lý Dirichlet, chắc chắn sẽ có ít nhất một “chuồng” chứa nhiều hơn một “con bồ câu”.

Bước 3: Suy luận từ việc có nhiều “con bồ câu” trong cùng một “chuồng”.

Giả sử hai số nguyên trong nhóm 101 số đã cho, gọi là \( a \) và \( b \), rơi vào cùng một “chuồng”. Điều này có nghĩa là \( a \) và \( b \) có cùng số dư khi chia cho 100.

Nói cách khác, tồn tại hai số nguyên \( k_1 \) và \( k_2 \) sao cho:
\( a = 100 \cdot k_1 + r \)
\( b = 100 \cdot k_2 + r \)
trong đó \( r \) là số dư chung của \( a \) và \( b \) khi chia cho 100 (với \( 0 \le r \le 99 \)).

Bây giờ, chúng ta xét hiệu của hai số này:
\( a – b = (100 \cdot k_1 + r) – (100 \cdot k_2 + r) \)
\( a – b = 100 \cdot k_1 + r – 100 \cdot k_2 – r \)
\( a – b = 100 \cdot k_1 – 100 \cdot k_2 \)
\( a – b = 100 \cdot (k_1 – k_2) \)

Vì \( k_1 \) và \( k_2 \) là các số nguyên, \( k_1 – k_2 \) cũng là một số nguyên. Do đó, \( a – b \) là một bội số của 100.

Điều này chứng tỏ rằng hiệu \( a – b \) chia hết cho 100.

Kết luận:

Chúng ta đã chứng minh được rằng, trong một nhóm 101 số nguyên, luôn tồn tại hai số có hiệu chia hết cho 100. Phương pháp sử dụng để chứng minh là Nguyên lý Dirichlet.

—

Vậy, đáp án đúng của chúng ta là:

B. Nguyên lý Dirichlet

Hy vọng qua bài giải này, các em đã hiểu rõ hơn về cách áp dụng Nguyên lý Dirichlet vào giải quyết các bài toán chứng minh. Đây là một công cụ rất mạnh mẽ mà các em nên làm quen. Nếu có bất kỳ câu hỏi nào, đừng ngần ngại đặt câu hỏi nhé!