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…)