Ứng dụng của nguyên lý Dirichlet trong giải toán THCS

TÀI LIỆU TOÁN HỌC

1

ỨNG DỤNG CỦA NGUYÊN LÝ DIRICHLET

TRONG CÁC BÀI TOÁN TỔ HỢP, SỐ HỌC, HÌNH HỌC

VÀ BẤT ĐẲNG THỨC TOÁN TRUNG HỌC CƠ SỞ

CHỦ ĐỀ 1:

CÁC BÀI TOÁN ỨNG DỤNG NGUYÊN LÝ DIRICHLET

TRONG CÁC BÀI TOÁN TỔ HỢP, SỐ HỌC VÀ HÌNH HỌC

I. Nguyên lí Dirichlet.

Nguyên lí Dirichlet - còn gọi là nguyên lí chim bồ câu (The Pigeonhole Principle)

hoặc nguyên lý những cái lồng nhốt thỏ hoặc nguyên lí sắp xếp đồ vật v|o ngăn kéo (The

Drawer Principle) - đưa ra một nguyên tắc về phân chia phần tử các lớp.

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ỏ.

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.

TÀI LIỆU TOÁN HỌC

2

II. 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.

III. Một số ví dụ minh họa.

Ví dụ 1. Cho bảng ô vuông kích thước 10.10 gồm 100 ô vuông đơn vị. Điền v|o mỗi ô

vuông của bảng n|y một số nguyên dương không vượt qu{ 10 sao cho hai số ở hai ô

vuông chung cạnh hoặc chung đỉnh nguyên tố cùng nhau. Chứng minh rằng trong bảng ô

vuông đã cho có một số xuất hiện ít nhất 17 lần.

Lời giải

Xét hình vuông cạnh 2x2 , do hình vuông n|y có mỗi hình vuông nhỏ luôn chung

cạnh hoặc chung đỉnh nên tồn tại nhiều nhất 1 số chẵn, nhiều nhất 1 số chia hết cho 3 do

đó có ít nhất 2 số lẻ không chia hết cho 3. Bảng 10x10 được chia th|nh 25 hình vuông có

cạnh 2x2 nên có ít nhất 50 số lẻ không chia hết cho 3. Từ 1 đến 0 có 3 số lẻ không chia hết

cho 3 là 1, 5, 7. Áp dụng nguyên lí Dirichlet ta được một trong ba số trên xuất hiện ít

nhất      

50 1 17 3 lần

TÀI LIỆU TOÁN HỌC

3

Ví dụ 2. Giả sử 1 bàn cờ hình chữ nhật có 3x7 ô vuông được sơn đen hoặc trắng. Chứng

minh rằng với c{ch sơn m|u bất kì thì trong bàn cờ luôn tồn tại hình chữ nhật gồm các ô ở

4 góc là các ô cùng màu.

Lời giải

Mẫu sơn m|u có thể xảy ra với bàn cờ này có dạng từ 1 đến 8. Giả sử một trong số

các cột thuộc dạng 1. Bài toán sẽ được chứng minh nếu tất cả các cột còn lại thuộc dạng 1,

2, 3 hoặc 4. Giả sử tất cả các cột còn lại thuộc dạng 5, 6, 7, 8 khi đó theo nguyên lí Dirichlet

thì hai trong số sau cột có 2 cột cùng 1 dạng v| như vậy b|i to{n cũng được chứng minh

Chứng minh ho|n to|n tương tự nếu 1 cột có dang 8. Giả sử không có cột nào

trong các cột 1, 8 thì theo nguyên lí Dirichlet cũng có 2 cột cùng dạng v| b|i to{n cũng

đựoc chứng minh

Ví dụ 3. Trong hình chữ nhật kích thước 1.2 ta lấy  2 6n 1 điểm với n là số nguyên dương.

Chứng minh rằng tồn tại 1 hình tròn có bán kính 1 n chứa không ít hơn 4 trong số c{c điểm

đã cho.

Lời giải

Chia các cạnh của hình chữ nhật th|nh n đoạn v| 2n đoạn bằng nhau ,mỗi đoạn có

độ dài 1 n . Nối c{c điểm chia bằng c{c đường thẳng song songvới các cạnh của hình chữ

nhật ta …