Tài liệu: Nguyên tắc ''cái ngăn kéo'' là gì?

Tài liệu
Nguyên tắc ''cái ngăn kéo'' là gì?

Nội dung

NGUYÊN TẮC ''CÁI NGĂN KÉO'' LÀ GÌ?

 

Bây giờ có 6 quyển sách muốn đặt vào trong 5 chiếc ngăn kéo, có rất nhiều cách đặt, có ngăn kéo không đặt sách, có ngăn kéo đặt 1, 2 quyển... thậm chí là cả 6 quyển. Nhưng dù đặt thế nào thì ít nhất phải tìm ra trong 1 ngăn kéo đặt ít nhất 2 quyển sách bên trong.

Nếu mỗi ngăn kéo đại diện cho một tập hợp, mỗi quyển sách đại diện cho một phần tử.

Giả sử có n+1 hoặc nhiều hơn n+1 phần tử phải đặt vào n tập hợp, vậy thì trong đó có ít nhất 1 tập hợp chứa ít nhất 2 phần tử bên trong. Đây chính là hàm nghĩa trừu tượng của ''nguyên tắc chiếc ngăn kéo''.

Ta hãy xét một ví dụ khác. Một lớp học có 54 học sinh, nếu 54 học sinh này đều sinh cùng 1 năm, vậy thì có ít nhất 2 người sinh cùng tuần. Tại sao lại như vậy? Vận dụng nguyên tắc ''chiếc ngăn kéo'' chúng ta sẽ dễ dàng hiểu ra. Do trong 1 năm chỉ có 53 tuần, vậy ta coi tuần là chiếc ngăn kéo, coi học sinh là sách, vậy trong 53 chiếc ngăn kéo có ít nhất 1 ngăn kéo đặt ít nhất 2 cuốn sách, hay chính là có ít nhất 2 học sinh sinh vào cùng một tuần.

Thường mà nói, số sách không cần thiết phải nhiều hơn 1 so với số ngăn kéo, có thể nhiều hơn một chút. Ví dụ: đặt 31 cuốn sách vào 5 chiếc ngăn kéo, cho dù đặt như thế nào thì ít nhất có thể tìm ra một ngăn kéo mà trong đó đặt ít nhất 7 cuốn sách. Nói cách khác, nếu đặt (m.n+1) hoặc nhiều hơn (m.n+1) phần tử vào trong n tập hợp, bất luận đặt như thế nào thì trong đó nhất định phải có ít nhất một tập hợp mà bên trong có đặt ít nhất m+1 nguyên tố.

Vận dụng nguyên tắc ''chiếc ngăn kéo'', còn có thể giải thích được ''câu hỏi 6 người tập hợp'' - trong 6 người tuỳ ý, có ít nhất 3 người từng bắt tay lẫn nhau hoặc có ít nhất 3 người chưa từng bắt tay nhau.




Nguồn: bachkhoatrithuc.vn/encyclopedia/207-26-633360033297812500/Toan-hoc/Nguyen-tac-cai-ngan-keo-la-gi.htm


Chưa có phản hồi
Bạn vui lòng Đăng nhập để bình luận