Nguyên tắc dirichlet

NGUYÊN TẮC ĐIRICLÊ

I. NỘI DUNG CỦA NGUYÊN TẮC ĐIRICLÊ
Nội dung của nguyên tắc này được phát biểu dưới dạng bài toán sau:
Nếu nhốt n thỏ vào m lồng, với n > m, nghĩa là số thỏ nhiều hơn số lồng, thì ít nhất cũng có một lồng nhốt không ít hơn 2 thỏ.

II. ĐỂ GIẢI CÁC BÀI TOÁN ÁP DỤNG NGUYÊN TẮC ĐIRICLÊ CHÚNG TA CẦN LƯU Ý MỘT SỐ ĐIỂM SAU ĐÂY:

1. Các bài toán áp dụng nguyên tắc Điriclê thường là các bài toán chứng minh sự tồn tại của sự vật, sự việc mà không cần phải chỉ ra một cách tường minh sự vật, sự việc đó.
2. Nhiều bài toán, nguyên tắc Điriclê chỉ xuất hiện sau khi biến đổi qua một bước trung gian, hoặc thành lập các dãy số mới.
3. Để giải bài toán áp dụng nguyên tắc Điriclê, nhiều khi ta phải kết hợp với phương pháp chứng minh phản chứng.
4. Khi giải các bài toán mà ta đã biết phải áp dụng nguyên tắc Điriclê hoặc dự đoán sẽ phải dùng nguyên tắc này, chúng ta cần suy nghĩ hoặc biến đổi bài toán để làm xuất hiện khái niệm "thỏ" và "lồng", khái niệm "nhốt thỏ vào lồng".
5. Cũng có thể có những bài toán phải áp dụng 2, 3 lần nguyên tắc Điriclê.
6. Trong suy nghĩ khi giải toán ta cố gắng làm xuất hiện các khái niệm "thỏ" và "lồng", nhưng trong trình bày phần lời giải ta cố gắng diễn đạt theo ngôn ngữ toán học thông thường.
7. Khi giải xong các bài toán áp dụng nguyên tắc Điriclê, chúng ta cố gắng suy nghĩ để sáng tạo ra được các bài toán tổng quát hơn hoặc cụ thể hơn. Vì chỉ có như thế ta mới thật nắm chắc bài toán mà mình đã làm.

BÀI TẬP:
1. Một đồi thông có 800 000 cây thông. Trên mỗi cây thông có không quá 500 000 chiếc lá. Chứng minh rằng ít nhất cũng có 2 cây thông có cùng số lá như nhau ở trên cây.
Bài giải:
Ta hãy tưởng tượng mỗi cây thông là một "thỏ", như vậy có 800.000 "thỏ" được nhốt vào không quá 500.000 "chiếc lồng". Lồng 1 ứng với cây thông có 1 chiếc lá trên cây, lồng 2 ứng với cây thông có 2 chiếc lá trên cây v.v... Số thỏ lớn hơn số lồng, theo nguyên tắc Điriclê ít nhất có 1 lồng nhốt không ít hơn 2 thỏ nghĩa là có ít nhất 2 cây thông có cùng số lá.
2. Một lớp học có 40 học sinh. Chứng minh rằng có ít nhất 4 học sinh có tháng sinh giống nhau.
Bài giải:
Một năm có 12 tháng. Ta phân chia 40 học sinh vào 12 tháng đó. Nếu mỗi tháng có không quá 3 học sinh được sinh ra thì số học sinh không quá: 3.12 = 36 mà 36 < 40: vô lý.
Vậy tồn tại một tháng có ít nhất 4 học sinh trùng tháng sinh ( trong bài này 40 thỏ là 40 học sinh, 12 lồng là 12 tên tháng).

3. Cho dãy số gồm 5 số tự nhiên bất kì a1, a2, a3, a4, a5. Chứng minh rằng tồn tại một số chia hết cho 5 hoặc tổng của một số số liên tiếp trong dãy đã cho chia hết cho 5.
Bài giải:
Ta sẽ thành lập dãy số mới gồm 5 số sau đây:
S1 = a1
S2 = a1 + a2
S3 = a1 + a2 + a3
S4 = a1 + a2 + a3 + a4
S5 = a1 + a2 + a3 + a4 + a5
- Nếu một trong cách Si (i = 1, ... 5) chia hết cho 5 thì bài toán đã được chứng minh.
- Nếu không có số nào chia hết cho 5 thì khi đem chia các số Si cho 5 sẽ được 5 số dư có giá trị từ 1 đến 4.
Có 5 số dư mà chỉ có 4 giá trị (5 thỏ, 4 lồng). Theo nguyên tắc Điriclê ít nhất phải có 2 số dư có cùng giá trị. Hiệu của chúng chia hết cho 5. Hiệu này chính là tổng các ai liên tiếp nhau hoặc là ai nào đó.

4. Với 39 số tự nhiên liên tiếp, hỏi rằng ta có thể tìm được một số mà tổng các chữ số của nó chia hết cho 11 hay không?
Bài giải:
Từ 20 số đầu tiên của dãy bao giờ ta cũng có thể tìm được 2 số mà chữ số hàng đơn vị là 0, và trong hai số đó ít nhất phải có một số có chữ số hàng chục khác 9. Giả sử N là số đó, và ta gọi S là tổng các chữ số của N.
Ta có dãy số mới N, N + 1, N + 2,... N + 9,