Chuyên đề: Nguyên lý Dirichle

ChuTieuThichHocToan xin giới thiệu với các cháu học sinh lớp 5,6 và các cháu THCS một số bài tập về Nguyên lý Dirichle (Nhốt thỏ vào chuồng). Đây là nguyên lý được phát biểu bởi nhà toán học Dirichle.  (Nếu để đến ngày nay, biết đâu lại có cháu nào phát biểu và lấy tên của mình đặt cho nguyên lý ấy cũng nên…)

I.      NGUYÊN LÝ DIRICHLET
Nguyên lí Dirichlet:

Không thể nhốt 7 chú thỏ vào 3 cái lồng sao cho mỗi lồng không quá 2 chú thỏ.

Có nhiều cách phát biểu, mở rộng nguyên lý này. Ví dụ nếu nhốt 3 con thỏ vào 2 chuồng thì bao giờ cũng tồn tại 1 chuồng chứa ít nhất 2 con thỏ…

Nguyên lí Dirichlet tổng quát:
Nếu đặt n viên bi vào k cái hộp (n,k nguyên dương), n = kq + r (với 0 < r < k) thì sẽ tồn tại một hộp chứa ít nhất q + 1 viên bi.

Chứng minh rất đơn giản: giả sử không hộp nào chứa nhiều hơn hoặc bằng q + 1 viên bi, khi đó k hộp sẽ chứa nhiều nhất k.q < n viên bi (vô lý)

Nguyên lí Dirichlet (còn gọi là nguyên lí chuồng bồ câu) tuy có phát biểu đơn giản nhưng lại được vận dụng rất nhiều trong thực tế. Nhờ nguyên lí này mà trong nhiều trường hợp, người ta dễ dàng chứng minh được sự tồn tại mà không đưa ra được phương pháp tìm kiếm cụ thể.

  (more…)

Advertisements