Câu hỏi 116
Người quản ngục đề nghị với các tù nhân trò chơi sau. Tất cả sẽ được đưa ra sân, ở đó mỗi người sẽ bị đội lên đầu một chiếc mũ có một trong 5 màu có thể. Sau đó người quản ngục xếp họ thành một hàng sao cho mỗi tù nhân nhìn thấy tất cả các mũ trừ mũ của chính mình, và hỏi tù nhân đầu tiên trong hàng xem anh ta có biết màu mũ của mình không. Tù nhân trả lời to "có" hoặc "không". Nếu trả lời "không", anh ta lập tức bị nhốt vào phòng biệt giam. Nếu trả lời "có", người quản ngục sẽ hỏi màu mũ của anh ta là gì, và tù nhân phải trả lời sao cho các tù nhân khác không nghe thấy câu trả lời. Nếu câu trả lời sai, tù nhân đó lập tức bị nhốt vào phòng biệt giam trước mặt mọi người, còn nếu câu trả lời đúng, tù nhân đó lập tức được thả trước mặt mọi người. Sau đó người quản ngục đến chỗ tù nhân tiếp theo trong hàng và lặp lại quy trình tương tự, và cứ như vậy cho đến tù nhân cuối cùng. Các tù nhân có thể nghĩ ra chiến lược trước khi trò chơi bắt đầu, nhưng khi trò chơi đã bắt đầu thì không được phép liên lạc với nhau. Nếu trong nhà tù có 2015 tù nhân thì số tù nhân lớn nhất được đảm bảo sẽ được thả là bao nhiêu nếu các tù nhân áp dụng chiến lược tối ưu?