Câu hỏi 58
Ngày xửa ngày xưa có $n$ cặp hoàng tử và công chúa yêu nhau. Một ngày nọ, một mụ phù thủy xuất hiện và biến tất cả các hoàng tử thành ếch; có thể phân biệt các con ếch bằng mắt nhưng các công chúa không biết con ếch nào tương ứng với hoàng tử nào. Mụ phù thủy nói với các công chúa rằng nếu công chúa nào hôn con ếch tương ứng với hoàng tử mà nàng yêu thì con ếch đó sẽ lập tức biến trở lại thành hoàng tử. Nếu mỗi công chúa chỉ chịu được việc hôn nhiều nhất $k$ con ếch, thì số hoàng tử lớn nhất mà các nàng chắc chắn cứu được là bao nhiêu?
(Các công chúa có thể lần lượt hôn theo thứ tự bất kỳ, trao đổi với nhau và thay đổi chiến lược cho các nụ hôn sau tùy theo thông tin thu được từ các nụ hôn trước.)
(Các công chúa có thể lần lượt hôn theo thứ tự bất kỳ, trao đổi với nhau và thay đổi chiến lược cho các nụ hôn sau tùy theo thông tin thu được từ các nụ hôn trước.)