Mỗi thành viên trong câu lạc bộ Toán tin có quê ở 1 trong 20 tỉnh thành. Hỏi cần phải tuyển bao nhiêu thành viên để đảm bảo có ít nhất 5 người cùng quê?
Đáp án đúng: A
Đây là một bài toán về nguyên lý Dirichlet (hay còn gọi là nguyên lý chuồng bồ câu). Nguyên lý này phát biểu rằng nếu có n chuồng bồ câu và nhiều hơn n con bồ câu, thì phải có ít nhất một chuồng chứa nhiều hơn một con bồ câu.
Trong bài toán này, ta có thể coi 20 tỉnh thành là 20 "chuồng". Chúng ta muốn tìm số lượng thành viên tối thiểu (số lượng "bồ câu") để đảm bảo có ít nhất 5 người cùng quê (ít nhất một "chuồng" chứa ít nhất 5 "bồ câu").
Để giải bài toán này, ta xét trường hợp xấu nhất, tức là ta cố gắng phân bố thành viên sao cho không có 5 người nào cùng quê. Trong trường hợp này, mỗi tỉnh thành sẽ có tối đa 4 người. Vậy, với 20 tỉnh thành, ta có thể có tối đa 20 * 4 = 80 người.
Tuy nhiên, nếu ta tuyển thêm 1 người nữa (tức là tổng cộng 81 người), thì theo nguyên lý Dirichlet, người này phải có cùng quê với một trong số 80 người đã được tuyển trước đó. Do đó, sẽ có ít nhất một tỉnh thành có 5 người (4 người ban đầu + 1 người mới).
Vậy, cần tuyển ít nhất 81 thành viên để đảm bảo có ít nhất 5 người cùng quê.
Bộ 525 câu hỏi trắc nghiệm ôn thi môn Toán rời rạc có đáp án dưới đây sẽ là tài liệu ôn tập hữi ích dành cho các bạn sinh viên. Mời các bạn cùng tham khảo!
