ITOT 42 mùa Xuân 2021 - THPT bảng A - luyện tập cộng điểm Câu hỏi 5

Có đoàn 100 du khách tới khách sạn có các phòng đơn đánh số $1,2,\ldots,n$. Ngoài $k$ phòng đang sửa chữa mà họ không biết số, các phòng còn lại đều trống. Mỗi khách lần lượt kiểm tra phòng theo một thứ tự có thể khác nhau giữa các khách, rồi vào phòng đầu tiên không sửa chữa. Họ không biết phòng có người trước khi tự kiểm tra, nhưng kiểm tra phòng người khác đang nghỉ là điều cấm kị. Họ phải thống nhất chiến lược trước. Với mỗi $k$, tìm $n$ nhỏ nhất bảo đảm chọn phòng phù hợp. (8 điểm)



Minh họa trung tính do người biên soạn tạo.