Chuyên đề: Nguyên lý Dirichlet trong Số học và Tổ hợp

Tài liệu gồm 26 trang, trích từ sách “Phân dạng và phương pháp giải toán số học và tổ hợp” của tác giả Nguyễn Quốc Bảo. Chuyên đề trình bày hệ thống lý thuyết, phương pháp và các dạng bài tiêu biểu liên quan đến Nguyên lý Dirichlet (Nguyên lí chim bồ câu), một công cụ quan trọng trong nhiều bài toán số học, tổ hợp và hình học.

A. Kiến thức cần nhớ

1. Giới thiệu Nguyên lý Dirichlet

Nguyên lý Dirichlet (hay nguyên lí “chim bồ câu – cái lồng”) phát biểu rằng:

Nếu có nhiều hơn nnn đối tượng được đặt vào nnn ngăn, thì tồn tại ít nhất một ngăn chứa từ hai đối tượng trở lên.

Đây là nguyên lý nền tảng để chứng minh sự tồn tại của một đối tượng hoặc cặp đối tượng thỏa mãn điều kiện nhất định.

2. Các dạng mở rộng của Nguyên lý Dirichlet

• Nguyên lý Dirichlet cơ bản

Nếu có $kn+1$ đối tượng và $n$ ngăn, thì có một ngăn chứa ít nhất $k+1$ đối tượng.

• Nguyên lý Dirichlet tổng quát

Nếu $m$ đối tượng được phân vào $n$ ngăn, thì tồn tại ngăn có ít nhất $[frac{m}{n}]$ đối tượng.

• Nguyên lý Dirichlet mở rộng

Áp dụng khi đối tượng hoặc ngăn không đồng đều, hoặc khi điều kiện yêu cầu tìm giá trị lớn nhất/nhỏ nhất.

• Nguyên lý Dirichlet trong dạng tập hợp

Xây dựng các tập hợp có tính chất đặc biệt rồi chứng minh hai phần tử buộc phải rơi vào cùng một tập hợp, từ đó thỏa mãn điều kiện cần tìm.

3. Phương pháp ứng dụng

Để vận dụng nguyên lý này hiệu quả, thường tiến hành:

• Xác định “đối tượng” (thỏ) và “ngăn” (lồng).
• Phân loại ngăn theo tính chất bài toán (số dư, vị trí, đặc điểm hình học,…).
• Dựa vào số lượng đối tượng lớn hơn số ngăn để kết luận tồn tại phần tử đặc biệt.

B. Các dạng toán thường gặp

Dạng 1. Chứng minh sự tồn tại chia hết

Mô hình hóa:

• các số tự nhiên ⇒ “thỏ”,
• các số dư khi chia cho $n$n ⇒ “lồng”.

Có $n$ lồng: lồng $i$ chứa những số có số dư $i$ (với $0≤i≤n−1$).

So sánh số lượng thỏ và lồng để chứng minh tồn tại hai số có cùng số dư, hoặc một tổng nào đó chia hết cho $n$.

Dạng 2. Bài toán về tính chất các phần tử trong tập hợp

Chiến lược:

• Tạo các tập hợp con theo tính chất phù hợp.
• Dùng Dirichlet để chứng tỏ tồn tại hai phần tử thuộc cùng một tập hợp.
• Từ đó suy ra sự tương đồng, trùng giá trị hoặc một điều kiện cần chứng minh.

Dạng 3. Bài toán liên quan đến bảng ô vuông

Áp dụng cho:

• bảng $n×n$: có $n$ hàng, $n$ cột và 2 đường chéo (mỗi hàng/cột/đường chéo có $n$ ô),
• bảng $m×n$: $m$ hàng, $n$ cột.

Ý tưởng: xem hàng/cột/đường chéo là các ngăn, xem các ô hoặc các đối tượng được đặt lên bảng là thỏ.

Dùng Dirichlet để chứng minh sự lặp lại, trùng vị trí hoặc tồn tại hai đối tượng nằm trên cùng cấu trúc.

Dạng 4. Bài toán thực tế

Trong các bài toán đời sống, mục tiêu thường là chứng minh sự tồn tại đối tượng, sự trùng lặp hoặc ràng buộc nào đó. Điều quan trọng nhất là:

• xác định đúng thỏ và lồng,
• phân loại lồng theo điều kiện bài cho,
• từ đó kết luận về sự tồn tại.

Dạng 5. Bài toán về sắp xếp

Các bài toán phân công, xếp chỗ, bố trí lịch,… thường không đòi hỏi tính toán phức tạp mà dựa vào:

• suy luận logic,
• phân chia khả năng xảy ra,
• dùng Dirichlet để chỉ ra có một trường hợp phải trùng nhau.

Dạng 6. Vận dụng Nguyên lý Dirichlet vào hình học

Một số kết quả điển hình:

1. Trên đoạn thẳng độ dài $1$:
   Nếu đặt nhiều đoạn thẳng có tổng độ dài $> 1$⇒ có ít nhất hai đoạn thẳng giao nhau.
2. Trên đường tròn bán kính $1$:
   Nếu đặt nhiều cung có tổng độ dài $> 2π$ ⇒ có hai cung có điểm chung.
3. Trong hình có diện tích $S$:
   Nếu đặt các hình có tổng diện tích $> S$ ⇒ có hai hình chồng lấn.

Các bài toán hình học thường quy đổi diện tích/độ dài thành “lồng”, còn các hình/cung/đoạn thành “thỏ”.

C. Bài tập áp dụng

Phần bài tập gồm các dạng từ cơ bản đến nâng cao:

• chứng minh chia hết,
• bài toán tổ hợp – sắp xếp,
• bài toán hình học ứng dụng Dirichlet,
• các bài toán sáng tạo và lạ.

D. Hướng dẫn giải – Đáp số

Phần lời giải giúp học sinh:

• hiểu rõ phương pháp tư duy,
• biết cách lựa chọn “thỏ – lồng” phù hợp,
• vận dụng nguyên lý một cách linh hoạt.