Thế nào là nguyên tắc ô kéo?

“Có sáu quyển sách cần xếp vào năm ô kéo. Có nhiều cách xếp sách vào các ô kéo, có ô kéo không có quyển sách nào, có ô kéo có một quyển sách, hai quyển sách,…thậm chí xếp đến sáu quyển sách. Thế nhưng cho dù cách xếp thế nào cũng có thể có một ô kéo ít nhất có hai quyển sách.

Nếu xem mỗi ô kéo đại diện cho một tập hợp, mỗi quyển sách là một phần tử của tập hợp. Giả sử có n + 1 hoặc hơn n + 1 phần tử xếp vào n tập hợp, thì rõ ràng trong đó ít nhất có một tập hợp có hai yếu tố. Đó chính là ý nghĩa trừu tượng của nguyên tắc ô kéo.

Ta xét một số ví dụ sau đây: Trong một lớp có 54 học sinh, giả thiết các học sinh đều sinh ra trong cùng một năm, thế thì ít nhất có hai học sinh được sinh ra trong cùng một tuần lễ. Vì sao lại như vậy? Dùng nguyên tắc ô kéo chúng ta lí giải điều đó khá dễ dàng.

Vì mỗi năm có 53 tuần lễ, ta xem mỗi tuần lễ như một ô kéo, xem mỗi học sinh như một quyển sách. Như vậy trong 53 ô kéo ít nhất có một ô kéo có hai quyển sách, nên ít nhất có thể có hai học sinh sinh ra trong cùng một tuần lễ.

Nói chung số quyển sách không nhất thiết chỉ nhiều hơn số ô kéo một quyển, mà có thể nhiều hơn. Ví dụ có 31 quyển sách xếp vào năm ô kéo. Bất kể là cách xếp sách như thế nào, ít nhất có một ô kéo được xếp đến bảy quyển sách. Tổng quát hơn nếu có m x n + 1 hoặc lớn hơn m x n + 1 phần tử xếp vào n tập hợp, thì cho dù chọn cách xếp như thế nào, trong đó ít nhất có 1 tập hợp có m +1 yếu tố.

Vận dụng nguyên tắc ô kéo ta có thể giải “bài toán nhóm 6 người”. Trong nhóm 6 người bất kì ít nhất có 3 người nắm tay nhau, hoặc ít nhất có 3 người chưa hề nắm tay nhau. Xin các bạn thử xem.”

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Hỏi đáp & Tư vấn © 2013 Hỏi đáp tư vấn