Các bài toán về nguyên lý Dirichlet trong số học

CHINH PHỤC KỲ THI HỌC SINH GIỎI CẤP HAI

A. KiÕn thøc cÇn nhí

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

Dirichlet (Đi-rích-lê) (1805 – 1859) là nhà

toán học người Đức, được cho là người đưa

ra định nghĩa hiện đại về hàm số. Trên cơ sở

quan sát thực tế, ông đã phát biểu thành

một nguyên lí mang tên ông – nguyên lí

Dirichlet: Không thể nhốt 7 con thỏ vào 3 cái

lồng mà mỗi cái lồng có không quá 2 con thỏ.

Nói cách khác, nếu nhốt 7 con thỏ vào 3 cái

lồng thì tồn tại ít nhất một lồng có từ 3 con trở

lên. Một cách tổng quát hơn, nếu có k lồng

để nhốt m con thỏ (với

k kn r = + (0 1) r k < ≤ − ) thì tồn tại ít nhất

một lồng có chứa từ n + 1 con thỏ trở lên.

Ta cũng có thể dễ dàng chứ minh nguyên lí Dirichet bằng phương pháp phản

chứng như sau: Giả sử không có một lồng nào chứ n + 1 con thỏ trở lên, tức là mỗi lồng

chứa nhiều nhất n con thỏ, thì số con thỏ chứa trong k lồng nhiều nhất chỉ có thể là kn con.

Điều này mâu thuẫn với giả thiết có m con thỏ với m kn r = + (0 1) r k < ≤ − .

Nguyên lí Dirichlet thật đơn giản, dễ hiểu nhưng được vận dụng vào giải rất nhiều bài

toán trong số học, đại số, hình học về việc chỉ ra sự tồn tại của một hay nhiều đối tượng

thỏa mãn một điều kiện đặt ra.

Khi sử dụng nguyên lí Dirichlet vào bài toán cụ thể, điều quan trọng là phải nhận ra (hay

tạo ra) Lồng hoặc Thỏ hoặc cả Lồng và Thỏ.

2. Một số dạng áp dụng của nguyên lý Dirichlet

• Nguyên lý Dirichlet cơ bản: Nếu nhốt + n 1 con thỏ vào n cái chuồng thì bao giờ cũng có

một chuồng chứa ít nhất hai con thỏ.

CHỦ ĐỀ

8

NGUYÊN LÝ DIRICHLET

TRONG SỐ HỌC

TỦ SÁCH CẤP 2| 202

BỒI DƯỠNG HỌC SINH GIỎI CẤP 2 |

CHUYÊN ĐỀ SỐ HỌC

• Nguyên lý Dirichlet tổng quát: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại

một hộp chứa ít nhất      

N k đồ vật. (Ở đây   x là số nguyên nhỏ nhất có giá trị nhỏ hơn

hoặc bằng x)

• Nguyên lí Dirichlet mở rộng: Nếu nhốt n con thỏ vào ≥ m 2 cái chuồng thì tồn tại một

chuồng có ít nhất  + −    

n m 1 m con thỏ.

• Nguyên lí Dirichlet dạng tập hợp: Cho A và B là hai tập hợp khác rỗng có số phần tử

hữu hạn, mà số lượng phần tử của A lớn hơn số lượng phần tử của B. Nếu với một quy tắc

nào đó, mỗi phần tử của A cho tương ứng với một phần tử của B, thì tồn tại ít nhất hai

phần tử khác nhau của A mà chúng tương ứng với một phần tử của B.

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

Nguyên lí Dirichlet tưởng chừng như đơn giản như vậy, nhưng nó là một công cụ

hết sức có hiệu quả dùng để chứng mình nhiều kết quả hết sức sâu sắc của toán học.

Nguyên lí Dirichlet cũng được áp dụng cho các bài toán của hình học, điều đó được thể

hiện qua hệ thống bài tập sau:

Để sử dụng nguyên lý Dirichlet ta phải làm xuất hiện tình huống nhốt “thỏ” vào

“chuồng” và thoả mãn các điều kiện:

+ Số ‘thỏ” phải nhiều hơn số chuồng.

+ “Thỏ” phải được nhốt hết vào các “chuồng”, nhưng không bắt buộc chuồng nào

cũng phải có thỏ.

Thường thì phương pháp Dirichlet được áp dụng kèm theo phương pháp phản

chứng. Ngoài ra nó còn có thể áp dụng với các nguyên lý khác. Một số bài toán cơ bản

thường gặp như sau:

1) Trong n + 1 số tự nhiên bất kì luôn tìm được hai số chia cho n có cùng số dư (hoặc

hiệu của chúng chia hết cho n ).

2) Nếu trên một đoạn thẳng độ dài 1 đặt một số đoạn thẳng có tổng độ dài lớn hơn 1

thì có ít nhất hai trong số các đoạn thẳng đó có điểm chung.

3) Nếu trên đường tròn có bán kính 1 đặt một số cung có tổng độ dài lớn hơn π 2 thì

có ít nhất hai trong số các cung đó có điểm chung.

4) Trong một hình có diện tích S đặt một số hình có tổng diện tích lớn hơn S thì có ít

nhất hai trong số các hình đó có điểm chung.

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

* Cơ sở phương pháp:

.203 | CHUYÊN ĐỀ SỐ HỌC