Nguyên lý Dirichlet

Dirichlet là nhà toán học người Đức (13/2/1805 - 5/5/1859)
Nguyên lý Dirichlet về số con thỏ và chuồng thỏ là một trong những nguyên lý cơ bản, cực kỳ dễ hiểu và rất dễ hình dung bằng hình ảnh. Tuy đơn giản nhưng dựa vào nguyên lý này hàng loạt các vấn đề toán học được giải quyết. Đối với nguyên lý này người ta chỉ chứng minh được sự tồn tại chứ không chỉ ra được phương pháp tìm vật cụ thể. Tuy nhiên có một số vấn đề trong toán học chỉ cần chỉ ra sự tồn tại cũng là quá đủ rồi.

Nội dung nguyên lý.

Dạng 1: Có $n$ phần tử cho vào $k$ tập thì tồn tại ít nhất một tập có nhiều hơn$\left[\dfrac{n}{k}\right]+1$ phần tử. Trong đó $\left[\dfrac{n}{k} \right]$ là phần nguyên của $\dfrac{n}{k}$.

Dạng 2: (Phát biểu theo kiểu ánh xạ) Cho hai tập $A,B$, trong đó tập $A$ có $n+1$ phần tử, tập $B$ có $n$ phần tử. Xét một ánh xạ đi từ $A\to B$. Khi đó tồn tại hai phần tử của $A$ có chung ảnh thuộc $B$ (tức là $\exists x_1,x_2 \in A : f(x_1)=f(x_2)$).

"Để làm dạng toán này đầu tiên ta cần phải làm quen một số bài toán dễ cơ bản để  làm nền và có cảm nhận, sau đó khi đọc bài toán ta phải tìm cách xây dựng được một mô hình mà ở đó có thể vận dụng được nguyên lý Dirichlet. Việc xây dựng được mô hình hợp lý logic để giải quyết bài toán phụ thuộc vào tư duy và lối logic của mỗi người, nó không tuân theo một quy tắc nào cả."

Một số bài toán ứng dụng của nguyên lý Dirichlet.

1. Một số bài toán ứng dụng trong thực tế.

Bài 1: Trong một hội trường có 400 đại biểu. Chứng minh rằng có ít nhất $2$ đại biểu có cùng ngày và tháng sinh.

Tutorial.

Một năm bất kỳ có nhiều nhất $366$ ngày (năm nhuận). Có $400$ đại biểu trong hội trường. Theo nguyên lý Dirichlet tồn tại ít nhất một ngày có nhiều hơn hai đại biểu được sinh. Tức là luôn có hai đại biểu sinh cùng ngày.

Bài 2: Các nghiên cứu về sinh học chỉ ra rằng số tóc trên đầu của một người không vượt quá $200,000$ sợi. Chứng minh rằng trong số hơn $1,500,000$ người dân ở Bình Định luôn có ít nhất $8$ người có cùng số sợi tóc.

Tutorial.

"Một đề bài quá ảo diệu, nếu như tưởng tượng thì chắc khó mà tin, làm sao biết có $8$ người cùng số tóc? Gần như không thể kiểm chứng, nhưng bằng nguyên lý Dirichlet ta chỉ ra được là trên thực tế nó lại đúng @@."

Bài 1: Chứng minh rằng một đường thẳng bất kỳ không đi qua đỉnh của một tam giác luôn cắt tối đa $2$ điểm nằm trên các cạnh của một tam giác.

Ý tưởng:

"Một bài toán đọc mang tính hiển nhiên quá cao, nhưng sử dụng nguyên lý Dirichlet ta lại dễ dàng chứng minh được"

Một đường thẳng luôn chia mặt phẳng thành hai phần. Có $3$ đỉnh. Theo nguyên lý Dirichlet thì tồn tại một phần của mặt phẳng chứa nhiều hơn $2$ đỉnh.

TH1: Chứa cả 3 đỉnh. Khi đó thì $(d)$ không cắt tam giác.

TH2: Chứa $2$ đỉnh. Khi đó $(d)$ cắt tam giác tại hai điểm.

Suy ra điều phải chứng minh.

Bài 2: Giả sử trong mặt phẳng mỗi điểm tô một trong hai màu trắng hoặc đen. Chứng minh rằng tồn tại một hình chữ nhật có 4 đỉnh cùng màu.

Ý tưởng:

"Đây là đề thi Olympic dành cho sinh viên. Nếu như chưa tiếp cận thì việc đọc xong đề bài toán gần như ta không có một chút hình dung nào về nó cả, tóm lại là hại não. Vì bài toán không có bất kỳ một dữ kiện gì."

Vì mỗi điểm trong mặt phẳng đều được đánh một trong hai màu trắng hoặc đen. Ta xét hình chữ nhật có kích thước $3\times 9$

o--o--o--o--o--o--o--o--o

o--o--o--o--o--o--o--o--o

o--o--o--o--o--o--o--o--o

Xét trên cột thứ nhất. Có $3$ vị trí, mà mỗi vị trí chỉ được đánh một trong hai màu trắng hoặc đen. Theo nguyên lý Dirichlet thì tồn tại ít nhất một màu có nhiều hơn hai vị trí. (Nói dễ hình dung hơn là sẽ tồn tại hai điểm cùng màu.)

Có tổng cộng $8$ cách tô màu cho $3$ vị trí. (Một vị trí là $2$, ba vị trí là $2^3=8$)

Có $9$ cột. Có $8$ cách tô. Theo nguyên lý Dirichlet có ít nhất một cách tô có nhiều hơn hai cột. (Nói dễ hiểu là tồn tại $2$ cột được tô y chang nhau.)

Vậy có $2$ cột được tô giống nhau, mà trên mỗi cột có $2$ điểm cùng màu. Suy ra có một hình chữ nhật có $4$ đỉnh cùng màu. (đpcm)

Bài 3: Cho $6$ điểm không có $3$ điểm nào thẳng hàng. Mỗi đoạn thẳng nối $2$ điểm được tô một trong hai màu đỏ hoặc đen. Chứng minh rằng tồn tại một tam giác có các đỉnh cùng màu.

Ý tưởng:

Vì $6$ điểm không thẳng hàng nên $3$ điểm bất kỳ luôn tạo thành một tam giác.

Giả sử $6$ điểm là $A,B,C,D,E,F$. Không mất tính tổng quát ta chọn $A$ làm gốc. Nối các đoạn $AB,AC,AD,AE,AF$. Có tổng cộng $5$ đoạn, mỗi đoạn có $2$ cách tô màu đỏ hoặc đen. Theo nguyên lý Dirichlet thì tồn tại ít nhất một màu tô nhiều hơn $3$ đoạn. Không mất tính tổng quát ta giả sử $3$ đoạn $AB,AC,AD$ được tô màu đỏ.

Khi đó $3$ đoạn $BC,CD,DB$, với $2$ cách tô màu thì theo nguyên lý Dirichlet cũng tồn tại một màu được tô nhiều hơn $2$ đoạn.

TH1: Nếu $BC,CD,DB$ được tô cùng màu đen. Tức tam giác $BCD$ thỏa yêu cầu bài toán. Ta có đpcm.

TH2: Tồn tại ít nhất một cạnh màu đỏ. Không mất tính tổng quát giả sử là $BC$. Khi đó tam giác $ABC$ thỏa yêu cầu bài toán. Ta cũng có đpcm.

Bài 4: Cho một tam giác đều cạnh là $1$. Chấm $5$ điểm phân biệt bất kỳ trong tam giác. Chứng minh rằng tồn tại ít nhất $2$ điểm có khoảng cách nhỏ hơn $0,5$.

Ý tưởng:

"Đây là một trong những bài nền tảng, nên nhớ làm nền để từ đó có thể vận dụng cho các bài tập phức tạp hơn"

Chia tam giác đều thành $4$ phần bằng nhau. (Cách chia là lấy trung điểm của cạnh khi đó số tam giác đều được chia là $2^2=4$, mở rộng thì số tam giác đều được chia bằng nhau là một số chính phương. Tức là nếu ta chia cạnh thành $3$ phần bằng nhau ta sẽ được $9$ tam giác đều, tương tự cho $16,25,36\ldots$)

Có $5$ điểm đặt vào $4$ tam giác đều. Theo nguyên lý Dirichlet thì tồn tại một tam giác đều chứ nhiều hơn hai điểm.(Nói dễ hình dung là tồn tại tam giác đều chứa $2$ điểm) Mà mỗi tam giác đều có cạnh lớn nhất là $0,5$. Ta suy ra đpcm.

Một số bài tương tự.

Bài 4.1 Trong một hình vuông cạnh $1$. Chấm $51$ điểm phân biệt. Chứng minh có $3$ điểm nằm trong đường tròn có bán kính $\dfrac{1}{7}$.